Presented at the Fifth International Workshop on Taylor Model Methods, Fields Institute, Toronto, May 23, 2008. Submitted for publication.
Fulltext.pdf (draft submitted July 2008; updated references [7] and [8] on May 19, 2009)
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 taxonomical results, known and new, 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.