About the hardness of reachability for ordinary differential equations and discrete time dynamical systems or Why analog mechanical machines of the 30's are not less powerful than modern computers, and not even slower.

9^th July 2015, 11:00 Ashton Lecture Theater
Prof Olivier Bournez
Computer Science Laboratory
Ecole Polytechnique (LIX)
Palaiseau Cedex
France

Abstract

In this talk we will discuss the hardness of solving reachability questions for dynamical systems over a continuous space. They include discrete time dynamical systems of the form y(t+1)=f(y(t)) and continuous time dynamical systems of the form y'=f(y(t)) where ' denotes derivative.

For both of them some computability results where known, but not much was know about the complexity of the problems. We will in particular explain why talking about time complexity is not at all a trivial problem for ordinary differential equations over an unbounded domain, by discussing several previous attempts in literature, and why they intrinsically mostly failed.

We will show that the continuous time case where f is a vector of polynomials is nice and related to questions about some old and new analog models of computations.

We will show in particular that one can numerically solve such ordinary differential equations in polynomial time in the length of the solution curve. Furthermore, we will show that one can embed the simulation of a Turing machine in such a setting. Consequently, systems of the form y(t+1)=f(y(t)) where f is a vector of polynomials seems to provide a very nice theory of computability for continuous time systems.

In particular, we obtain for the first time a characterization of classical polynomial time, that is to say of complexity class P, in terms of ordinary differential equations only.