Improved lower bounds on the number of multiplications/divisions which are necessary to evaluate polynomials |
| |
Authors: | C.P. Schnorr |
| |
Affiliation: | Fachbereich Mathematik, Universität Frankfurt, Robert Mayer Stasse 6-10, 6 Frankfurt, Federal Republic of Germany |
| |
Abstract: | We improve some lower bounds which have been obtained by Strassen and Lipton. In particular there exist polynomials of degree n with 0–1 coefficients that cannot be evaluated with less than nonscalar multiplications/divisions. The evaluation of p(x) requires at least multiplications/divisions and at least nonscalar multiplications/divisions. We specify polynomials with algebraic coefficients that require multiplications/divisions. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|