Akitoshi Kawamura. Lipschitz continuous ordinary differential equations are polynomial-space complete. *Computational Complexity* **19**(2), 305–332, May 2010. DOI = 10.1007/s00037-010-0286-0

Akitoshi Kawamura. Lipschitz continuous ordinary differential equations are polynomial-space complete. In *Proceedings of the 24th Annual IEEE Conference on Computational Complexity* (CCC 2009), pages 149–160, Paris, France, July 2009. Awarded the **Ronald V. Book Prize for Best Student Paper**. DOI = 10.1109/CCC.2009.34 (but please refer to the journal version above)

**Full text on arXiv**(April 26, 2010)**Slide.pdf**(July 16, 2009; 25 minutes)

In answer to K. Ko's question (*Information and Control*, 1983),
we show that an initial value problem
given by a polynomial-time computable, Lipschitz continuous function
can have a polynomial-space complete solution.
The key insight is simple:
the Lipschitz condition means
that the feedback mechanism in the differential equation is very weak.
We define a discrete system with equally weak feedback,
and show that it is still polynomial-space complete.
The same technique also settles
the two conjectures on Volterra integral equations
later raised by Ko (STOC 1991).

- Key words
- computable analysis, computational complexity, exponential space, initial value problem, Lipschitz condition, ordinary differential equations, Picard–Lindelöf Theorem, polynomial space, Volterra integral equations