*salle A. Turing CE4*

3 September 2015 - 14h00

On the complexity of some continuous space reachability problems

by Amaury Pouly from LIX (Polytechnique)

Abstract: In this talk, I will present some results about the two reachability problems of some continuous space. 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 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.