A1 Refereed original research article in a scientific journal
The membership problem for subsemigroups of GL2(Z) is NP-complete
Authors: Bell Paul C, Hirvensalo Mika, Potapov Igor
Publisher: ACADEMIC PRESS INC ELSEVIER SCIENCE
Publishing place: SAN DIEGO
Publication year: 2024
Journal: Information and Computation
Journal name in source: INFORMATION AND COMPUTATION
Journal acronym: INFORM COMPUT
Article number: 105132
Volume: 296
Number of pages: 27
ISSN: 0890-5401
eISSN: 1090-2651
DOI: https://doi.org/10.1016/j.ic.2023.105132
Web address : https://doi.org/10.1016/j.ic.2023.105132
Self-archived copy’s web address: 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/).
Downloadable publication This is an electronic reprint of the original article. |  |
