On the complexity of the orbit problem Journal Article

Author(s): Chonev, Ventsislav K; Ouaknine, Joël; Worrell, James B
Article Title: On the complexity of the orbit problem
Affiliation IST Austria
Abstract: 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 NPRP.
Keywords: Linear recurrence sequences; Linear transformations; Matrix orbits; Skolem's problem; Termination of linear programs
Journal Title: Journal of the ACM
Volume: 63
Issue 3
ISSN: 0004-5411
Publisher: ACM  
Date Published: 2016-06-01
Start Page: Article number: 23
DOI: 10.1145/2857050
Open access: yes (repository)