On the Polytope Escape Problem for continuous linear dynamical systems

The Polytope Escape Problem for continuous linear dynamical systems consists of deciding, given an affine function f : R^d → R^d and a convex polytope P in R^d, both with rational descriptions, whether there exists an initial point x₀ in P such that the trajectory of the unique solution to the differential equation x'(t) = f(x(t)), x(0) = x₀, t ≥ 0, is entirely contained in P. We show that this problem is reducible in polynomial time to the decision version of linear programming with real algebraic coefficients.The latter is a special case of the decision problem for the existential theory of real closed fields, which is known to lie between NP and PSPACE. Our algorithm makes use of spectral techniques and relies, among others, on tools from Diophantine approximation.

Proceedings of HSCC 17, 2017. 7 pages.

PDF © 2017 Joël Ouaknine, João Sousa Pinto, and James Worrell.