On the Polytope Escape Problem for Continuous Linear Dynamical Systems

The Polyhedral Escape Problem for continuous linear dynamical systems consists of deciding, given an affine function $f: $\mathbb{R}$^{d} \rightarrow $\mathbb{R}$^{d}$andaconvexpolyhedron$$\mathcal{P}$ \subseteq $\mathbb{R}$^{d}$, whether, for some initial point ${\mathit{x}}_0$ in $\mathcal{P}$, the trajectory of the unique solution to the differential equation $\dot{\mathit{x}}(t)=f(\mathit{x}(t))$, $\mathit{x}(0)={\mathit{x}}_0$, is entirely contained in $\mathcal{P}$. We show that this problem is decidable, by reducing it in polynomial time to the decision version of linear programming with real algebraic coefficients, thus placing it in $\mathrm{\exists }\mathbb{R}$, which lies between NP and PSPACE. Our algorithm makes use of spectral techniques and relies among others on tools from Diophantine approximation.