On the Complexity of the Orbit Problem

2013/03/12 by Chonev, Ventsislav, Ouaknine, Joël, Worrell, James
#Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #F.2.1 #FOS: Computer and information sciences #G.2.1

paper · doi:10.48550/arxiv.1303.2981

Abstract

We consider higher-dimensional 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 NP^RP.

Related

• Orbit Problem Revisited
• Deciding subspace reachability problems with application to Skolem's Problem
• The Polyhedron-Hitting Problem
• Orbit decidability, applications and variations
• Semialgebraic Invariant Synthesis for the Kannan-Lipton Orbit Problem