# Complexity of Initial Value Problems

Presented at the Fifth International Workshop on Taylor Model Methods, Fields Institute, Toronto, May 23, 2008. To appear in *Fields Institute Communications*.

Fulltext.pdf (updated in December 2011)

## Abstract

How complex could the solution be to
an initial value problem given by a polynomial-time computable function?
This question can be given a natural and precise sense
in computational complexity theory.
We answer the question by several (known and new) results
stating that more conditions on the problem make the solution simpler.
In particular,
Lipschitz continuity alone may leave the solution polynomial-space complete,
but analyticity makes the solution polynomial-time computable.