Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR08-052 | 22nd May 2008 00:00

The Orbit problem is in the GapL hierarchy Revision of: TR08-052

RSS-Feed




Revision #1
Authors: Vikraman Arvind, T.C. Vijayaraghavan
Accepted on: 22nd May 2008 00:00
Downloads: 2070
Keywords: 


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.


Paper:

TR08-052 | 29th April 2008 00:00

The Orbit problem is in the GapL Hierarchy





TR08-052
Authors: Vikraman Arvind, T.C. Vijayaraghavan
Publication: 19th May 2008 04:23
Downloads: 1306
Keywords: 


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.



ISSN 1433-8092 | Imprint