The membership problem for subsemigroups of \(\operatorname{GL}_2(\mathbb{Z})\) is \textbf{NP}-complete
From MaRDI portal
Publication:6178465
DOI10.1016/j.ic.2023.105132OpenAlexW4390128471MaRDI QIDQ6178465
Mika Hirvensalo, Igor Potapov, Paul C. Bell
Publication date: 18 January 2024
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ic.2023.105132
NP-completenessgeneral linear groupspecial linear groupmatrix semigroupscompressed data structurescomputational group theorynonnumerical algorithms
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- SL(2, Z) symmetries, supermembranes and symplectic torus bundles
- Reachability problems in quaternion matrix and rotation semigroups
- Non-Euclidean visibility problems
- The boundedness of all products of a pair of matrices is undecidable
- Knapsack in graph groups
- On theories with a combinatorial definition of 'equivalence'
- On the decidability of semigroup freeness
- Mortality for 2 ×2 Matrices Is NP-Hard
- Learning Weighted Automata
- Composition Problems for Braids
- On the Complexity of Nash Equilibria and Other Fixed Points
- ON THE UNDECIDABILITY OF THE IDENTITY CORRESPONDENCE PROBLEM AND ITS APPLICATIONS FOR WORD AND MATRIX SEMIGROUPS
- On the Complexity of the Orbit Problem
- Musical intervals and special linear transformations
- ON THE UNDECIDABILITY OF FREENESS OF MATRIX SEMIGROUPS
- Decidability of the Membership Problem for 2 × 2 integer matrices
- The Identity Problem for Matrix Semigroups in SL2(ℤ) is NP-complete
- Vector Reachability Problem in SL(2, Z)
- Solvability of Matrix-Exponential Equations
- Stable mixing for cat maps and quasi-morphisms of the modular group
- Some decision problems on integer matrices
- Arithmetic Applications of the Hyperbolic Lattice Point Theorem
- On the Complexity of Equivalence and Minimisation for Q-weighted Automata
- On the Identity Problem for the Special Linear Group and the Heisenberg Group.
- TC^0 circuits for algorithmic problems in nilpotent groups
- Polynomial-time theory of matrix groups
- Decidable and Undecidable Problems about Quantum Automata
- On Termination of Integer Linear Loops
- Membership Problem for the Modular Group
- The Compressed Word Problem for Groups
- Mortality Problem for 2×2 Integer Matrices
- Knapsack problems in groups
- Unsolvability in 3 × 3 Matrices
- Theory Is Forever
