## The Orbit Problem in higher dimensions

*Ventsislav Chonev*, *Joel
Ouaknine*, and *James Worrell*
We consider higher-dimensional versions of Kannan and Lipton's Orbit
Problem -- determining whether a target vector space *V* may be
reached from a starting point *x* under repeated applications of a
linear transformation *A*. Answering two questions posed by Kannan
and Lipton in the 1980s, we show that when *V* has dimension one, this
problem is solvable in polynomial time, and when *V* has dimension two
or three, the problem is in **NP**^{RP}.

*Proceedings of STOC 13*, 2013. 9 pages.

PDF
© 2013 ACM.