### Polynomial-time algorithm for the orbit problemPolynomial-time algorithm for the orbit problem

Access Restriction
Subscribed

 Author Kannan, R. ♦ Lipton, R. J. Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©1986 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Abstract The accessibility problem for linear sequential machines [12] is the problem of deciding whether there is an input $\textit{x}$ such that on $\textit{x}$ the machine starting in a given state $q_{1}$ goes to a given state $q_{2}.$ Harrison shows that this problem is reducible to the following simply stated linear algebra problem, which we call the "orbit problem":Given (n, A, x, y), where $\textit{n}$ is a natural number and A, x, and $\textit{y}$ are $n^{x}n,$ $n^{x}1,$ and $n^{x}1$ matrices of rationals, respectively, decide whether there is a natural number $\textit{I}$ such that $A^{i}x=y.He$ conjectured that the orbit problem is decidable. No progress was made on the conjecture for ten years until Shank [22] showed that if $\textit{n}$ is fixed at 2, then the problem is decidable. This paper shows that the orbit problem for general $\textit{n}$ is decidable and indeed decidable in polynomial time. The orbit problem arises in several contexts; two of these, linear recurrences and the discrete logarithm problem for polynomials, are discussed, and we apply our algorithm for the orbit problem in these contexts. 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 1986-08-10 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 33 Issue Number 4 Page Count 14 Starting Page 808 Ending Page 821

#### Open content in new tab

Source: ACM Digital Library