Solving Analytic Differential Equations in Polynomial Time over Unbounded Domains

Olivier Bournez (1) , Daniel Graça (2) , Amaury Pouly (1)

1 LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau]
2 FCT - Faculdade de Ciências e Tecnologia [Faro]

In this paper we consider the computational complexity of solving initial-value problems defined with analytic ordinary differential equations (ODEs) over unbounded domains in $\R^n$ and $\C^n$. We show that the solution can be computed in polynomial time over its maximal interval of definition, provided it satisfies a very generous bound on its growth, and that the function admits an analytic extension over a strip on the complex plane.

Domains: Computer Science [cs]; Computational Complexity [cs.CC]

Olivier Bournez, Daniel Graça, Amaury Pouly. Solving Analytic Differential Equations in Polynomial Time over Unbounded Domains. Mathematical Foundations of Computer Science, MFCS'11, 2011, Poland. pp.170-181. ⟨hal-00760919⟩