The orbit problem in higher dimensions

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 .

Authors

• Ventsislav Chonev
• Joël Ouaknine
• James Worrell 0001

Keywords

• Skolem's problem
• matrix powers
• orbit problem