5
$\begingroup$

why do we need the restriction on the degree for a polynomial to be in VP due to which $(\prod_{i=0}^{n} x_i)^{2^n}$ $\notin$ VP even though it has a poly-size circuit?

$\endgroup$
10
$\begingroup$

It's not really needed, so much as it is a matter of convention and utility. Of course, depending on your aims and your specific problem, it is completely reasonable to consider arithmetic circuits of polynomial size regardless of degree. This class is often denoted $\mathsf{VP}_{nb}$ (for "Non-degree-Bounded"), or sometimes "algebraic $\mathsf{P/poly}$ or $\mathsf{algP/poly}$.

I was curious about this same question for a long time, so a while ago I spent some time digging. I found both a posteriori motivations, based on what we now know, and more historical, a priori motivations. I'm sure this list is incomplete, but here's what I found.

A priori motivations:

  1. Skyum and Valiant [A Complexity Theory Based on Boolean Algebra. J. ACM 32(2):484-502, 1985] seems to make it clear that the real motivation is that in the Boolean setting p-bounded degree is what we have, since every function can be expressed as a multilinear (and hence degree $\leq n$) polynomial. See (2), (3), and (4) below.

  2. Valiant’s original paper (Valiant. Completeness classes in algebra. STOC 1979) is focused on formula size, and his original definition of p-definable is given in terms of multilinear polynomials whose coefficients have poly size formulae, and then taking the closure under p-projections. The motivation for p-projections is clear. This yields p-bounded degree as a consequence.

  3. One motivation for considering formula size: ”We note that in the Boolean case, although no analogue of Hyafil’s result is known, the logarithm of formula size is intimately related to the space required to compute the function.” [Valiant, p. 11] (We now know that, in the Boolean case, polynomial formula size is equivalent to nonuniform $\mathsf{NC}^1$ (log-depth, poly-size circuits), but at the time I do not know if this class was yet considered.)

  4. Another motivation for formula size from the Boolean case (which he discusses in Section 9): Boolean p-definable families exactly capture $\mathsf{NP/poly}$ – that is, the only difference between "Boolean p-definable" and "$\mathsf{NP}$" is nonuniformity. (The use of multilinearity in his definition of p-definable may also have been motivated by this, since all Boolean functions can be written multilinearly.)

  5. Strassen’s result on eliminating divisions multiplies the complexity by a factor of $deg^2$, so maintaining polynomial complexity while eliminating divisions uses p-bounded degree.

  6. For quasipolynomial instead of polynomial bounds, we have qp-computable iff qp formula size, but only for families of qp-bounded degree. This follows from two results that were known at the time: Hyafil (1979) showed that depth is at most $O((\log d + \log s)\log d)$, where $d$ is the degree and $s$ is the circuit size, and Brent (1974) showed that depth is $\Theta(\log(\text{formula size}))$

  7. Without the restriction on degree, permanent would not be $\mathsf{VNP}$-complete under p-projections, as any p-projection of permanent has p-bounded degree.

A posteriori motivations:

  1. Valiant-Skyum-Berkowitz-Rackoff [SIAM J. Comput. 12(4):641-644, 1983] extends Hyafil’s result to yield circuits of the same depth as Hyafil, but whose size is polynomial in the original size and the degree.

  2. The more recent depth-reduction results (the chasms at depth 3 and 4) also involve the degree of the polynomial. As with VSBR, they become significantly less powerful for polynomials of large degree (and trivial for polynomials of really large degree).

  3. von zur Gathen’s “Feasible Arithmetic Computations: Valiant’s Hypothesis” [J. Symb. Comput. (1987) 4, 137-172] provides several useful reasons for bounding the degree. In particular, by bounding the degree in the definition of $\mathsf{VNP}$, $\mathsf{VNP}$ is closed under many natural operations that it would not otherwise be closed under. See esp. the two paragraphs at the top of p. 156 mentioning results of Kaltofen (1986) and Plaisted (1984).

  4. von zur Gathen, ibid., p. 7: "Restricting the degree is quite reasonable over infinite fields, e.g. over $\mathbb{Q}$, where the binary representation of the value of a polynomial like $x^{2^n}$ has exponential length even for small inputs. In a different setting–over varying finite fields–natural problems like the trace, testing for quadratic residuosity, or factoring polynomials, lead to polynomials of large degree, which can nevertheless be computed efficiently (yon zur Gathen & Seroussi, 1986)."

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.