The orbit problem is in the GapL hierarchy
The Orbit problem is defined as follows: Given a matrix A is an element of Q(nxn) and vectors x, y is an element of 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-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.
orbit problem linear algebra parallel complexity logspace counting classes parallel algorithm