On the complexity of the orbit problem

DOI10.1145/2857050zbMATH Open1426.68116arXiv1303.2981OpenAlexW2963416205MaRDI QIDQ3177796FDOQ3177796

James Worrell, Joël Ouaknine, Ventsislav Chonev

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 (20)

• On the Mortality Problem: From Multiplicative Matrix Equations to Linear Recurrence Sequences and Beyond
• 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
• The membership problem for subsemigroups of \(\operatorname{GL}_2(\mathbb{Z})\) is \textbf{NP}-complete
• Solving Skolem's problem for the \(k\)-generalized Fibonacci sequence with negative indices
• On the identity and group problems for complex Heisenberg matrices
• Porous invariants for linear systems
• First-order orbit queries
• 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
• 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?
• O-Minimal Invariants for Discrete-Time 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)