2009 24th Annual IEEE Conference on Computational Complexity Lipschitz Continuous Ordinary Differential Equations are Polynomial-Space Complete Paris, France July 15-July 18 ISBN: 978-0-7695-3717-7
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/CCC.2009.34
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 restricted feedback, and show that they are still polynomial-space complete. The same technique also settles Ko's two later questions on Volterra integral equations.
Index Terms:
computable analysis, computational complexity, initial value problem, Lipschitz condition, ordinary differential equations, Picard
Citation:
Akitoshi Kawamura, "Lipschitz Continuous Ordinary Differential Equations are Polynomial-Space Complete," ccc, pp.149-160, 2009 24th Annual IEEE Conference on Computational Complexity, 2009 Usage of this product signifies your acceptance of the Terms of Use. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb