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)


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.