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

DOI10.1016/J.IC.2023.105132MaRDI QIDQ6178465zbMATH OpenOpenAlexFDO

Authors Paul C. Bell, Mika Hirvensalo, Igor Potapov

Publication date 18 January 2024

Published in Information and Computation (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1016/j.ic.2023.105132

zbMATH Keywords

NP-completenessgeneral linear groupmatrix semigroupscompressed data structuresspecial linear groupcomputational group theorynonnumerical algorithms

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• scientific article; zbMATH DE number 6677405 (Why is no real title available?)
• scientific article; zbMATH DE number 3585537 (Why is no real title available?)
• scientific article; zbMATH DE number 7204378 (Why is no real title available?)
• scientific article; zbMATH DE number 2232304 (Why is no real title available?)
• Arithmetic Applications of the Hyperbolic Lattice Point Theorem
• Composition problems for braids
• Decidability of the membership problem for \(2\times 2\) integer matrices
• Decidable and Undecidable Problems about Quantum Automata
• Knapsack in graph groups
• Knapsack problems in groups
• Learning weighted automata
• Membership Problem for the Modular Group
• Mortality Problem for 2×2 Integer Matrices
• Mortality for \(2 \times 2\) matrices is NP-hard
• Musical intervals and special linear transformations
• Non-Euclidean visibility problems
• ON THE UNDECIDABILITY OF FREENESS OF MATRIX SEMIGROUPS
• On termination of integer linear loops
• On the Complexity of Equivalence and Minimisation for Q-weighted Automata
• On the Complexity of Nash Equilibria and Other Fixed Points
• On the Identity Problem for the Special Linear Group and the Heisenberg Group.
• On the complexity of the orbit problem
• On the computational complexity of matrix semigroup problems
• On the decidability of semigroup freeness.
• On the undecidability of the identity correspondence problem and its applications for word and matrix semigroups
• On theories with a combinatorial definition of 'equivalence'
• Polynomial-time theory of matrix groups
• Reachability problems in quaternion matrix and rotation semigroups
• SL(2, Z) symmetries, supermembranes and symplectic torus bundles
• Solvability of Matrix-Exponential Equations
• Some decision problems on integer matrices
• Stable mixing for cat maps and quasi-morphisms of the modular group
• The Compressed Word Problem for Groups
• The boundedness of all products of a pair of matrices is undecidable
• The identity problem for matrix semigroups in \(\mathrm{SL}_2(\mathbb{Z})\) is NP-complete
• Theory Is Forever
• Unsolvability in 3 × 3 Matrices
• Vector reachability problem in \(\operatorname{SL}(2,\mathbb{Z})\)
• \(\mathsf{TC}^0\) circuits for algorithmic problems in nilpotent groups

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

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