The membership problem for subsemigroups of GL2(Z) is NP-complete.

Bell, Paul C, Hirvensalo, Mika and Potapov, Igor (2023) The membership problem for subsemigroups of GL2(Z) is NP-complete. Information and Computation, 296. p. 105132.

PDF
BelHirPot24.pdf - Author Accepted Manuscript
Download (1MB) | Preview

Official URL: http://dx.doi.org/10.1016/j.ic.2023.105132

Abstract

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 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 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 GL2(Z) is NP-complete, and the group problem and the non-freeness problem in SL2(Z) are NP-complete. 1

Item Type:	Article
Divisions:	Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science
Depositing User:	Symplectic Admin
Date Deposited:	09 Apr 2024 10:48
Last Modified:	09 Apr 2024 15:01
DOI:	10.1016/j.ic.2023.105132
Related URLs:	Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3180232