The Orbit problem is defined as follows: Given a matrix A ∈ Q n×n and vectors x, y ∈ Q n , does there exist a non-negative integer i such that A i x = y. This problem was shown to be in deterministic polynomial time by Kannan and Lipton (J. ACM 33(4): [808][809][810][811][812][813][814][815][816][817][818][819][820][821] 1986). In this paper we place the problem in the logspace counting hierarchy GapLH. We also show that the problem is hard for C = L with respect to logspace many-one reductions.
Let us also mention the more recent work of Arvind and Vijayaraghavan REF which places the original Orbit Problem in the logspace counting hierarchy GapLH.