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.
