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

Mathematics Subject Classification ID

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)

The membership problem for subsemigroups of \(\operatorname{GL}_2(\mathbb{Z})\) is \textbf{NP}-complete ⋮ Matrix Semigroup Freeness Problems in SL $$(2,\mathbb {Z})$$ ⋮ Vector Ambiguity and Freeness Problems in SL $$(2,\mathbb {Z})$$ ⋮ On the Identity Problem for the Special Linear Group and the Heisenberg Group. ⋮ Vector and scalar reachability problems in \(\operatorname{SL}(2, \mathbb{Z})\) ⋮ Relations in the semigroup of 2 × 2 upper-triangular matrices ⋮ Unnamed Item ⋮ On the mortality problem: from multiplicative matrix equations to linear recurrence sequences and beyond ⋮ 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

This page was built for publication: The Identity Problem for Matrix Semigroups in SL₂(ℤ) is NP-complete