ECCC-Report TR08-052https://eccc.weizmann.ac.il/report/2008/052Comments and Revisions published for TR08-052en-usThu, 22 May 2008 00:00:00 +0300
Revision 1
| The Orbit problem is in the GapL hierarchy Revision of: TR08-052 |
Vikraman Arvind,
T.C. Vijayaraghavan
https://eccc.weizmann.ac.il/report/2008/052#revision1The \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.
Thu, 22 May 2008 00:00:00 +0300https://eccc.weizmann.ac.il/report/2008/052#revision1
Paper TR08-052
| The Orbit problem is in the GapL Hierarchy |
Vikraman Arvind,
T.C. Vijayaraghavan
https://eccc.weizmann.ac.il/report/2008/052The \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.
Mon, 19 May 2008 04:23:37 +0300https://eccc.weizmann.ac.il/report/2008/052