Computational complexity of computing polynomials over the fields of real and complex numbers

DOI10.1145/800133.804344MaRDI QIDQ5402553zbMATH OpenOpenAlexFDO

Authors Victor Y. Pan

Publication date 14 March 2014

Published in Proceedings of the tenth annual ACM symposium on Theory of computing - STOC '78 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/800133.804344

zbMATH Keywords

evaluationpreconditioningpolynomialcomplexity of computationnumber of arithmetic operationslower bounds of complexityoptimal schemes of computationscheme of computationupper bounds of complexity

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computation over the reals, computable analysis (03D78) Complexity of computation (including implicit computational complexity) (03D15)

Recommendations

• Polynomials with Rational Coefficients Which are Hard to Compute
• scientific article; zbMATH DE number 4070302
• Fields of algebraic numbers computable in polynomial time. I
• Polynomial computability of fields of algebraic numbers
• Complexity of Computations with Matrices and Polynomials

Cited in

(9)

• scientific article; zbMATH DE number 4070302 (Why is no real title available?)
• Polynomials with Rational Coefficients Which are Hard to Compute
• Piecewise algebraic functions
• Evaluation of complex polynomials in one and two variables
• Lower bounds in algebraic computational complexity
• A logarithmic Boolean time algorithm for parallel polynomial division
• Algebraic complexity of computing polynomial zeros
• Computation of Minkowski values of polynomials over complex sets
• The Computational Complexity of Division in Quadratic Extension Fields

This page was built for publication: Computational complexity of computing polynomials over the fields of real and complex numbers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5402553)