A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
The membership problem for subsemigroups of GL2(Z) is NP-complete
Tekijät: Bell Paul C, Hirvensalo Mika, Potapov Igor
Kustantaja: ACADEMIC PRESS INC ELSEVIER SCIENCE
Kustannuspaikka: SAN DIEGO
Julkaisuvuosi: 2024
Journal: Information and Computation
Tietokannassa oleva lehden nimi: INFORMATION AND COMPUTATION
Lehden akronyymi: INFORM COMPUT
Artikkelin numero: 105132
Vuosikerta: 296
Sivujen määrä: 27
ISSN: 0890-5401
eISSN: 1090-2651
DOI: https://doi.org/10.1016/j.ic.2023.105132
Verkko-osoite: https://doi.org/10.1016/j.ic.2023.105132
Rinnakkaistallenteen osoite: https://research.utu.fi/converis/portal/detail/Publication/387052597
We show that the problem of determining if the identity matrix belongs to a finitely generated semigroup of 2 x 2 matrices from the General Linear Group GL2(Z) is solvable in NP. We extend this to prove that the membership problem is decidable in NP for GL2(Z) and for any arbitrary regular expression over matrices from the Special Linear group SL2(Z). We show that determining if a given finite set of matrices from SL2(Z) or the modular group PSL2(Z) generates a group or a free semigroup are decidable in NP. Previous algorithms, shown in 2005 by Choffrut and Karhumaki, were in EXPSPACE. Our algorithm is based on new techniques allowing us to operate on compressed word representations of matrices without explicit expansions. When combined with known NPhard lower bounds, this proves that the membership problem over GL2(Z) is NP -complete, and the group problem and the non -freeness problem in SL2(Z) are NP -complete. 1 (c) 2023 The Authors. Published by Elsevier Inc. This is an open access article under the CC BY license (http://creativecommons .org /licenses /by /4 .0/).
Ladattava julkaisu This is an electronic reprint of the original article. |  |
