<p>It's not really <em>needed</em>, 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}$.</p>

<p>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.</p>

<p>A priori motivations:</p>

<ol>
<li><p>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.</p></li>
<li><p>Valiant’s original paper (Valiant. Completeness classes in
algebra. STOC 1979) is focused on <em>formula size</em>, 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.</p></li>
<li><p>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.)</p></li>
<li><p>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.)</p></li>
<li><p>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.</p></li>
<li><p>For quasipolynomial instead of polynomial bounds, we have
qp-computable iff qp formula size, but <em>only for families of
qp-bounded degree</em>. 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}))$</p></li>
<li><p>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.</p></li>
</ol>

<p>A posteriori motivations:</p>

<ol>
<li><p>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 <em>and the
degree</em>.</p></li>
<li><p>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).</p></li>
<li><p>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).</p></li>
<li><p>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 &amp; Seroussi,
1986)."</p></li>
</ol>

CC BY-SA 3.0
2013-10-03T16:24:13.067Z
2013-10-03T16:24:13.067Z
Joshua Grochow
<p>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?</p>

<algebraic-complexity><arithmetic-circuits><bounded-degree>
Degree restriction for polynomials in $\mathsf{VP}$
Tulasi
# Degree restriction for polynomials in $\mathsf{VP}$

(Asked by: username_0 on 2013-10-03)

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?

**Tags:** algebraic-complexity, arithmetic-circuits, bounded-degree

---

## 1 answers

### Answer by username_1 on 2013-10-03. Score: 12 | Accepted answer

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)."


---

