Author(s):

Chonev, Ventsislav K; Ouaknine, Joël; Worrell, James B

Article Title: 
On the complexity of the orbit problem

Affiliation 
IST Austria 
Abstract: 
We consider higherdimensional versions of Kannan and Lipton's Orbit Problem  determining whether a target vector space V may be reached from a starting point x under repeated applications of a linear transformation A. Answering two questions posed by Kannan and Lipton in the 1980s, we show that when V has dimension one, this problem is solvable in polynomial time, and when V has dimension two or three, the problem is in NPRP.

Keywords: 
Linear recurrence sequences; Linear transformations; Matrix orbits; Skolem's problem; Termination of linear programs

Journal Title:

Journal of the ACM

Volume: 
63

Issue 
3

ISSN:

00045411

Publisher:

ACM

Date Published:

20160601

Start Page: 
Article number: 23

URL: 

DOI: 
10.1145/2857050

Open access: 
yes (repository) 