Lipschitz Continuous Ordinary Differential Equations are Polynomial-Space Complete

Details Lipschitz Continuous Ordinary Differential Equations are Polynomial-Space Complete Lipschitz Continuous Ordinary Differential Equations are Polynomial-Space Complete

2010-04-26

arxiv.org/abs/1004.4622v1

Computational Complexity 19(2):305-332, May 2010

Computer Science

Computational Complexity

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

Scientific paper

10.1007/s00037-010-0286-0

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.

Affiliated with

Also associated with

No associations

Rating

Lipschitz Continuous Ordinary Differential Equations are Polynomial-Space Complete does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Lipschitz Continuous Ordinary Differential Equations are Polynomial-Space Complete, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Lipschitz Continuous Ordinary Differential Equations are Polynomial-Space Complete will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-33025