The Identity Problem for Matrix Semigroups in SL2(ℤ) is NP-complete
DOI10.1137/1.9781611974782.13zbMath1410.68139OpenAlexW4251324924MaRDI QIDQ4575748
Igor Potapov, Paul C. Bell, 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
Analysis of algorithms and problem complexity (68Q25) Free semigroups, generators and relations, word problems (20M05) Algebraic systems of matrices (15A30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (11)
This page was built for publication: The Identity Problem for Matrix Semigroups in SL2(ℤ) is NP-complete