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

DOI10.1137/1.9781611974782.13zbMATH Open1410.68139OpenAlexW4251324924MaRDI QIDQ4575748FDOQ4575748

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

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})\)

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)

Cited In (18)

• Vector and scalar reachability problems in \(\operatorname{SL}(2, \mathbb{Z})\)
• On the Identity Problem for the Special Linear Group and the Heisenberg Group.
• 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 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
• Subgroup membership in \(\mathrm{GL}(2, \mathrm{Z})\)
• Relations in the semigroup of \(2\times 2\) upper-triangular matrices
• 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
• Title not available (Why is that?)

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)