Lipschitz Continuous Ordinary Differential Equations are Polynomial-Space Complete

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)

Abstract

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