Skip to main navigation Skip to Content

Lipschitz Continuous Ordinary Differential Equations are Polynomial-Space Complete

Speaker: Akitoshi Kawamura, University of Toronto

Abstract:

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.