The membership problem for subsemigroups of \(\operatorname{GL}_2(\mathbb{Z})\) is \textbf{NP}-complete

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

zbMATH Keywords

NP-completenessgeneral linear groupspecial linear groupmatrix semigroupscompressed data structurescomputational group theorynonnumerical algorithms

Mathematics Subject Classification ID

Theory of computing (68Qxx)

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 SL₂(ℤ) 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

This page was built for publication: The membership problem for subsemigroups of \(\operatorname{GL}_2(\mathbb{Z})\) is \textbf{NP}-complete