NP in group theory


1.Membership (Decide whether a given matrix M belong to a semigroup) and two special cases such as: Identity (i.e. if M is the identity matrix) and Mortality (i.e. if M is the zero matrix) problems. The Identity problem in SL(2, Z) is NP-complete.


1.Vector reachability (Decide for a given vectors u and v whether exist a matrix M in S such that M · u = v).The vector reachability problem over a finitely generated semigroup of matrices from SL(2, Z) and the point to point reachability (over rational numbers) for fractional linear transformations, where associated matrices are from SL(2, Z) are decidable