Search

We show that the problem of determining if the identity matrix belongs to a finitely generated semigroup of 2 × 2 matrices from the General Linear Group GL 2 (Z) is solvable in NP. We extend this to prove that the membership problem is decidable in NP for GL 2 (Z) and for any arbitrary regular expression over matrices from the Special Linear group SL 2 (Z). We show that determining if a given finite set of matrices from SL 2 (Z) or the modular group PSL 2 (Z) generates a group or a free semigroup are decidable in NP. Previous algorithms, shown in 2005 by Choffrut and Karhumäki, 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 NP -hard lower bounds, this proves that the membership problem over GL 2 (Z) is NP -complete, and the group problem and the non-freeness problem in SL 2 (Z) are NP -complete. 1 [ABSTRACT FROM AUTHOR]