Lipschitz Continuous Initial Value Problem is Polynomial-Space Complete

(Yet) unpublished note.

Fulltext.pdf (draft, updated on March 11, 2008)

Abstract

We show, in answer to Ko's question in 1983, that the initial value problem given by a polynomial-time computable, Lipschitz continuous function can have a polynomial-space complete solution.