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

DOI10.1137/1.9781611974782.13MaRDI QIDQ4575748zbMATH OpenOpenAlexFDO

Authors Paul C. Bell, Igor Potapov, Mika Hirvensalo

Publication date 16 July 2018

Published in Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/1.9781611974782.13

Mathematics Subject Classification ID

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

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

(18)

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

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)