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

NP-completeness general linear group matrix semigroups compressed data structures special linear group computational group theory nonnumerical algorithms

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

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

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