Polynomial-time algorithm for the orbit problem
Ramachandran Kannan, R.J. Lipton · Journal of the ACM · 1986
The accessibility problem for linear sequential machines [12] is the problem of deciding whether there is an input x such that on 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 n is a natural number and A, x, and y are n x n , n x 1, and n x 1 matrices of rationals, respectively, decide whether there is a natural number 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 n is fixed at 2, then the problem is decidable. This paper shows that the orbit problem for general 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.