Lipschitz Continuous Ordinary Differential Equations are Polynomial-Space Complete

Abstract

In answer to Ko's question raised in 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 in the differential equation is weak. We define a class of polynomial-space computation tableaux with equally weak feedback, and show that they are still polynomial-space complete. The same technique also settles Ko's two later questions on Volterra integral equations.

22 pages, 9 figures; preliminary version presented at CCC 2009

Cited by in corpus (5)

• Computability and analysis: the legacy of Alan Turing
• Complexity Theory for Operators in Analysis
• Polynomial Time corresponds to Solutions of Polynomial Ordinary Differential Equations of Polynomial Length
• Computational complexity of solving polynomial differential equations over unbounded domains
• Computing the exact number of periodic orbits for planar flows