Abstract:
The \emph{Orbit problem} is defined as follows: Given a matrix $A\in \Q ^{n\times n}$ and vectors $\x,\y\in \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 in \cite{KL1986}. In this paper we place the problem in the logspace counting hierarchy $\GapLH$. We also show that the problem is hard for $\CeqL$ with respect to logspace many-one reductions.

Abstract:
The \emph{Orbit problem} is defined as follows: Given a matrix $A\in \Q ^{n\times n}$ and vectors $\x,\y\in \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 in \cite{KL1986}. In this paper we place the problem in the logspace counting hierarchy $\GapLH$. We also show that the problem is hard for $\L$ under $\NCone$-many-one reductions.