The Polyhedral Escape Problem is Decidable

Abstract. The Polyhedral Escape Problem for continuous linear dynamical systems con-sists of deciding, given an affine function f: Rd → Rd and a convex polyhedron P ⊂ Rd, whether, for some initial point x0 in P, the trajectory of the unique solution to the differ-ential equation ẋ(t) = f(x(t)),x(0) = x0, t ≥ 0, is entirely contained in 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 ∃R, which lies between NP and PSPACE. Our algorithm makes use of spectral techniques and relies among others on tools from Diophantine approximation.