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)
Take the 2-minute tour
×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.
|
|
|||||||||||||||||||||
|
|
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. |
|||||
|
