Lipschitz Continuous Ordinary Differential Equations are Polynomial-Space
Speaker: Akitoshi Kawamura, University of Toronto
How complex can the solution of a differential equation be,
compared to the function used to describe the equation?This question can be given a precise sense
consistent with the standard computational complexity theory.In this talk, I will first explain how we
define polynomial-time computability of real functions.Then I will discuss the complexity of the
solution of initial value problems of differential equations under various
assumptions.In particular, an initial
value problem given by a polynomial-time computable, Lipschitz continuous
function can have a polynomial-space complete solution.
This answers Ko's question raised in 1983.Time permitting, I will also mention what
these kinds of results about the complexity of possible solutions often imply
about the hardness of solving the differential equation.