On the complexity of the orbit problem

DOI10.1145/2857050zbMATH Open1426.68116OpenAlexW2963416205MaRDI QIDQ3177796FDOQ3177796

Authors Ventsislav Chonev, Joël Ouaknine, James Worrell

Publication date 2 August 2018

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1303.2981

zbMATH Keywords

linear transformationslinear recurrence sequencesSkolem's problemmatrix orbitstermination of linear programs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Recurrences (11B37) Linear transformations, semilinear transformations (15A04) Decidability (number-theoretic aspects) (11U05)

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}.

Recommendations

• The orbit problem in higher dimensions
• Polynomial-time algorithm for the orbit problem
• scientific article; zbMATH DE number 7204476
• The orbit problem is in the GapL hierarchy
• The polyhedron-hitting problem

Cited in

(26)

• On the identity and group problems for complex Heisenberg matrices
• The orbit problem is in the GapL hierarchy
• Model checking linear dynamical systems under floating-point rounding
• On the mortality problem: from multiplicative matrix equations to linear recurrence sequences and beyond
• On Affine Reachability Problems
• The orbit problem in higher dimensions
• The Orbit Problem Is in the GapL Hierarchy
• What's decidable about discrete linear dynamical systems?
• Polynomially ambiguous probabilistic automata on restricted languages
• scientific article; zbMATH DE number 7559425 (Why is no real title available?)
• On the mortality problem: from multiplicative matrix equations to linear recurrence sequences and beyond
• scientific article; zbMATH DE number 7559115 (Why is no real title available?)
• Identity testing for radical expressions
• Polynomially Ambiguous Probabilistic Automata on Restricted Languages
• On the complexity of Anosov saddle transitions
• The membership problem for subsemigroups of \(\operatorname{GL}_2(\mathbb{Z})\) is \textbf{NP}-complete
• Algebraic model checking for discrete linear dynamical systems
• On the Identity Problem for the Special Linear Group and the Heisenberg Group.
• The polyhedron-hitting problem
• Orbits of linear maps and regular languages
• Polynomial-time algorithm for the orbit problem
• Semialgebraic invariant synthesis for the Kannan-Lipton orbit problem
• Porous invariants for linear systems
• Solving Skolem's problem for the \(k\)-generalized Fibonacci sequence with negative indices
• Effective results on the Skolem problem for linear recurrence sequences
• First-order orbit queries

This page was built for publication: On the complexity of the orbit problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3177796)