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

complexity of real functionspolynomial-time computable real functionspolynomial-time computable real numberspower seriesTaylor coefficients

Mathematics Subject Classification ID

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

Review text

It is shown that if a real-valued function f is polynomial-time computable on [a,b], with \(a<0<b\), and is analytic at 0, then the Taylor coefficients of f at 0, as a sequence of real numbers, is polynomial-time computable. Here, the notion of polynomial-time computable real numbers and real functions is based on the formal definitions given by the authors [Theor. Comput. Sci. 20, 323-352 (1982; Zbl 0498.03047)].

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

• Computability and Noncomputability in Classical Analysis
• Computational complexity of real functions
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• 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)

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

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)