### On the Complexity of the Orbit ProblemOn the Complexity of the Orbit Problem

Access Restriction
Subscribed

 Author Chonev, Ventsislav ♦ Ouaknine, Joeumll ♦ Worrell, James Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2016 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword Linear transformations ♦ Skolem’s problem ♦ Linear recurrence sequences ♦ Matrix orbits ♦ Termination of linear programs Abstract We consider higher-dimensional versions of Kannan and Lipton’s Orbit Problem—determining whether a target vector space ν may be reached from a starting point $\textit{x}$ under repeated applications of a linear transformation $\textit{A}.$ Answering two questions posed by Kannan and Lipton in the 1980s, we show that when ν has dimension one, this problem is solvable in polynomial time, and when ν has dimension two or three, the problem is in $NP^{RP}.$ ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 2016-06-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 63 Issue Number 3 Page Count 18 Starting Page 1 Ending Page 18

#### Open content in new tab

Source: ACM Digital Library