12
$\begingroup$

By counting arguments, one can show that there exist polynomials of degree n in 1 variable (i.e., something of the form $a_n x^n + a_{n-1} x^{n-1} + \cdots + a_0)$ which have circuit complexity n. Also, one can show that a polynomial like $x^n$ requires at least $\log_2 n$ multiplications (you need that just to get a high enough degree). Are there any explicit examples of polynomials in 1 variable with a superlogarithmic lower bound on complexity? (results over any field would be interesting)

$\endgroup$
  • $\begingroup$ Are the examples you have in mind with circuit complexity $n$ over a finite field? I don't see how a counting argument would work over an infinite field, and over the rationals I'm pretty sure Paterson-Stockmeyer's $\sqrt{n}$ bound is tight (see also my answer below). $\endgroup$ – Joshua Grochow Nov 30 '10 at 4:33
  • $\begingroup$ The sqrt(n) bound you mention is just an upper bound on the number of multiplications (over any field), but if we count both additions and multiplications as operations, then we need n operations over an infinite field for almost every polynomial, just because there are n distinct coefficients in the polynomial and there's no way to evaluate all possible polynomials with less than n operations (I'm not sure if this should be called a counting argument or not). $\endgroup$ – matt hastings Nov 30 '10 at 22:04
  • $\begingroup$ I think you have to be a bit more precise in the statement "there's no way to evaluate all possible polynomials with less than n ops." One way to interpret that is: if we think of the polynomial $\sum a_i x^i$ as a polynomial not just in $x$, but also treat the $a_i$'s as variables (or, equivalently, suppose the $a_i$ are algebraically independent), then the result that this requires n additions is Pan's (1966) and is not just a counting argument (though it's not too difficult). Otherwise, I'm not quite sure what result you're referring to with that statement. $\endgroup$ – Joshua Grochow Dec 1 '10 at 3:04
  • 1
    $\begingroup$ What I mean is: the circuit consists of addition and multiplication gates. The inputs for a given gate can be outputs of previous gates, or x, or some constants. The question is: for a given polynomial, can we find a circuit and choice of constants in that circuit to compute it? But, we have an (n+1)-dimensional space of polynomials, but if we fix the structure of a circuit with less than n gates (by "structure", I mean which gates use outputs of which other gates) and consider all possible choices of constants this gives less than an n dimensional space of polynomials that can be computed. $\endgroup$ – matt hastings Dec 1 '10 at 15:45
  • $\begingroup$ Btw---the impression I get is that constructing explicit examples over R or C without further restrictions on the coefficients is mostly solved. On the other hand, constructing explicit examples where all the coefficients a_i are integers and not growing too rapidly, it still open? There is an example with all integer constants in the survey you mention, but they grow doubly exponentially. $\endgroup$ – matt hastings Dec 1 '10 at 15:51
11
$\begingroup$

Paterson and Stockmeyer show that for most $n$-tuples of rational numbers $(a_1, \dotsc, a_n)$, evaluating $\prod_{i=1}^{n} (x - a_i)$ requires $\Omega(\sqrt{n})$ arithmetic operations, and this is tight.

The following polynomials get within a logarithmic factor of the $\sqrt{n}$ bound, by results of Strassen, Schnorr, and Heintz & Sieveking: $\sum_{i=1}^{n} 2^{2^{i}} x^{i}$, $\sum_{i=1}^{n} e^{2 \pi i / 2^{i}} x^{i}$, $\sum_{i=1}^{n} i^{r} x^{i}$ (for $r$ a rational that is not an integer), etc. For exact references and for more on this, see pp. 324-325 of von zur Gathen's survey.

$\endgroup$
  • $\begingroup$ Thanks. So, it would seem that the open problem is that if you count additions also as operations, can one construct a polynomial which needs more than sqrt(n) operations, with the goal of constructing one which needs n operations. Any results towards this? (I doubt it, because in the method that needs only sqrt(n) multiplications, the additions give some matrix multiplication and this probably reduces to lower bounds on complexity of a matrix-scalar multiplication) $\endgroup$ – matt hastings Nov 30 '10 at 22:07

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.