On the complexity of the orbit problem

DOI10.1145/2857050zbMATH Open1426.68116arXiv1303.2981OpenAlexW2963416205MaRDI 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)

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

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

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

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)

Cited In (27)

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

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)