Some polynomials that are hard to compute

DOI10.1016/0304-3975(80)90020-1zbMath0442.68028OpenAlexW2034505758MaRDI QIDQ1143788

Joachim von zur Gathen, Volker Strassen

Publication date: 1980

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(80)90020-1

zbMATH Keywords

algebraic complexitypolynomial evaluationcomplexity of polynomials

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30)

Related Items

On Kolmogorov complexity in the real Turing machine setting ⋮ Simplified lower bounds for polynomials with algebraic coefficients ⋮ Time-space tradeoffs in algebraic complexity theory ⋮ A new method to obtain lower bounds for polynomial evaluation ⋮ On the representation of rational functions of bounded complexity

Cites Work

• Lower bounds for polynomials with algebraic coefficients
• Improved lower bounds on the number of multiplications/divisions which are necessary to evaluate polynomials
• Polynomials with Rational Coefficients Which are Hard to Compute