Name
Abstract | ||
|---|---|---|
The Orbit problem is defined as follows: Given a matrix A驴驴 n脳n and vectors x,y驴驴 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. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1007/s10878-009-9243-8 | Electronic Colloquium on Computational Complexity |
Keywords | Field | DocType |
gapl hierarchy,deterministic polynomial time,hierarchy gaplh,orbit problem,orbit problem · linear algebra · parallel complexity · logspace counting classes · parallel algorithm,many-one reduction,j. acm,linear algebra,polynomial time,parallel algorithm | Integer,Discrete mathematics,Linear algebra,Combinatorics,Matrix (mathematics),Parallel algorithm,Combinatorial optimization,Hierarchy,Time complexity,Deterministic system (philosophy),Mathematics | Journal |
Volume | Issue | ISSN |
21 | 1 | 1382-6905 |
Citations | PageRank | References |
5 | 0.66 | 7 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| V. Arvind | 1 | 122 | 12.03 |
| T. C. Vijayaraghavan | 2 | 19 | 3.54 |