On the complexity of some continuous space reachability problems

In this talk, I will present some results about two problems.  The first problem is that of region to region reachability for piecewise affine functions.  We show that, starting from dimension 2, the bounded time version is NP-complete, even if the function is assumed to be continuous.  The second problem is related to polynomial differential equations (system of ODEs of the form y'=p(y) where p is a polynomial).  We show that one can numerically solve such ODEs in polynomial time in the length of the solution curve.  Furthermore, we show that one can embed the simulation of a Turing machine in such a setting.  Consequently, some reachability problems for polynomial differential equations become P-complete.

Speaker biography

Amaury Pouly is currently finishing his PhD at the LIX (Polytechnique, France) under the supervision of Olivier Bournez and Daniel Graca.