Computing power series in polynomial time

DOI10.1016/0196-8858(88)90006-1MaRDI QIDQ1102956zbMATH OpenOpenAlexFDO

Authors Harvey M. Friedman, Ker-I Ko

Publication date 1988

Published in Advances in Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0196-8858(88)90006-1

zbMATH Keywords

power seriesTaylor coefficientspolynomial-time computable real functionscomplexity of real functionspolynomial-time computable real numbers

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computability and recursion theory on ordinals, admissible sets, etc. (03D60) Constructive and recursive analysis (03F60)

Recommendations

• scientific article; zbMATH DE number 4051615
• scientific article; zbMATH DE number 1746037
• Uniform computational complexity of the derivatives of \(C^{\infty}\)-functions.
• Characterizing polynomial time computability of rational and real functions
• Polynomial time computation in the context of recursive analysis

Cites work

• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Computability and Noncomputability in Classical Analysis
• Computational complexity of real functions
• Some negative results on the computational complexity of total variation and differentiation
• The computational complexity of maximization and integration
• The maximum value problem and NP real numbers

Cited in

(10)

• Rational presented metric spaces and complexity, the case of the space of real functions uniformly continuous on a compact interval
• Composing power series over a finite ring in essentially linear time
• Вычисление гипергеометрических рядов с квазилинейной временной и линейной eмкостной сложностью
• A simple and fast algorithm for computing exponentials of power series
• Average-case polynomial-time computability of Hamiltonian dynamics
• On parallel complexity of analytic functions
• scientific article; zbMATH DE number 4051615 (Why is no real title available?)
• Lower bounds on the continuation of holomorphic functions
• Computability of Differential Equations
• On subrecursive complexity of integration

This page was built for publication: Computing power series in polynomial time

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