## The Polyhedron-Hitting Problem

*Ventsislav Chonev*, *Joel
Ouaknine*, and *James Worrell*
We consider polyhedral versions of Kannan and Lipton's Orbit Problem [14,13] -- determining whether a
target polyhedron *V* may be reached from a starting point *x* under repeated applications of
a linear transformation *A* in an ambient vector space **Q**^{m}. In the context
of program verication, very similar reachability questions were also considered and left open by Lee
and Yannakakis in [15], and by Braverman in [4]. We present what amounts to a complete characterisation
of the decidability landscape for this problem, expressed as a function of the dimension *m* of
the ambient space, together with the dimension of the polyhedral target *V*: more precisely, for
each pair of dimensions, we either establish decidability, or show hardness for longstanding open
problems.

*Proceedings of SODA 15*, 2015. 17 pages.

PDF
© 2015 SIAM.