## On the Polyhedral Escape Problem for linear dynamical systems

*Joao Sousa Pinto*, *Joel
Ouaknine*, and *James Worrell*
The Polyhedral Escape Problem for continuous linear dynamical
systems consists of deciding, given an affine function
*f* : **R**^{d} → **R**^{d} and a
convex polyhedron
*P* in **R**^{d}, whether, for some initial point
*x*_{0} in *P*, 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 place this problem in
∃**R**, which lies between NP and PSPACE, by reducing it in
polynomial time to the decision version of linear programming with
real algebraic coefficients. Our algorithm makes use of spectral
techniques and relies among others on tools from Diophantine
approximation.

*Submitted*, 2016. 11 pages.

PDF
© 2016 Joao Sousa Pinto, Joel Ouaknine, and James Worrell.