The identity problem for matrix semigroups in SL₂(Z) is NP-complete

Algebraic systems of matrices (15A30) Free semigroups, generators and relations, word problems (20M05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Recommendations

Matrix semigroup freeness problems in \(\mathrm{SL}(2,\mathbb {Z})\)
On the computational complexity of matrix semigroup problems
On the correlation of symmetric functions
Some decision problems on integer matrices
Vector ambiguity and freeness problems in \(\mathrm{SL} (2,\mathbb {Z})\)

Cited in

(25)

Vector and scalar reachability problems in \(\operatorname{SL}(2, \mathbb{Z})\)
On the mortality problem: from multiplicative matrix equations to linear recurrence sequences and beyond
On the computational complexity of matrix semigroup problems
Matrix semigroup freeness problems in \(\mathrm{SL}(2,\mathbb {Z})\)
Vector ambiguity and freeness problems in \(\mathrm{SL} (2,\mathbb {Z})\)
Decidability of the membership problem for \(2\times 2\) integer matrices
On the correlation of symmetric functions
The complexity of the word-problem for finite matrix rings
Relations in the semigroup of \(2\times 2\) upper-triangular matrices
On generic complexity of the subset sum problem for semigroups of integer matrices
On the Identity Problem for the Special Linear Group and the Heisenberg Group.
Generic complexity of the membership problem for semigroups of integer matrices
On Affine Reachability Problems
On Reachability Problems for Low-Dimensional Matrix Semigroups
On the mortality problem: from multiplicative matrix equations to linear recurrence sequences and beyond
scientific article; zbMATH DE number 7204378 (Why is no real title available?)
The membership problem for subsemigroups of \(\operatorname{GL}_2(\mathbb{Z})\) is \textbf{NP}-complete
Subgroup membership in \(\mathrm{GL}(2, \mathrm{Z})\)
On the identity and group problems for complex Heisenberg matrices
Semigroup intersection problems in the Heisenberg groups
Ordering groups and the identity problem
Nonnegativity problems for matrix semigroups
The identity problem in the special affine group of \(\mathbb{Z}^2\)
Subgroup membership in GL\((2,\mathbb{Z})\)
On word representations and embeddings in complex matrices

This page was built for publication: The identity problem for matrix semigroups in \(\mathrm{SL}_2(\mathbb{Z})\) is NP-complete

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