The orbit problem is in the GapL hierarchy |
| |
Authors: | V Arvind T C Vijayaraghavan |
| |
Institution: | 1.Institute of Mathematical Sciences,Chennai,India;2.Chennai Mathematical Institute,Siruseri,India |
| |
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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|