## On the Polytope Escape Problem for continuous linear dynamical systems

*Joël
Ouaknine*, *João Sousa Pinto*, and *James Worrell*
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*_{0} in *P* such that the trajectory of
the unique solution to the differential equation
*x*'(*t*) = *f*(*x*(*t*)),
*x*(0) = *x*_{0}, *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.

Imprint / Data Protection