The Orbit problem is defined as follows: Given a matrix A∈Q{sup}(n×n) and vectors x, y∈Q{sup}n, does there exist a non-negative integer i such that A{sup}ix=y. This problem was shown to be in deterministic polynomial time by Kannan and Lipton in [7]. In this paper we put the problem in the logspace counting hierarchy GapLH. We also show that the problem is hard for C{sub}=L.
展开▼
