Revision #1 Authors: Vikraman Arvind, T.C. Vijayaraghavan

Accepted on: 22nd May 2008 00:00

Downloads: 3449

Keywords:

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.

TR08-052 Authors: Vikraman Arvind, T.C. Vijayaraghavan

Publication: 19th May 2008 04:23

Downloads: 2508

Keywords:

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.