The membership problem for subsemigroups of GL2(Z) is NP-complete
: Bell Paul C, Hirvensalo Mika, Potapov Igor
Publisher: ACADEMIC PRESS INC ELSEVIER SCIENCE
: SAN DIEGO
: 2024
: Information and Computation
: INFORMATION AND COMPUTATION
: INFORM COMPUT
: 105132
: 296
: 27
: 0890-5401
: 1090-2651
DOI: https://doi.org/10.1016/j.ic.2023.105132
: https://doi.org/10.1016/j.ic.2023.105132
: 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/).
UTU Research Portal