The complexity of the membership problem for 2-generated commutative semigroups of rational matrices
Jin‐Yi Cai, R.J. Lipton, Yechezkel Zalcstein · 2002
We present a deterministic polynomial-time algorithm for the ABC problem, which is the membership problem for 2-generated commutative linear semigroups over an algebraic number field. We also obtain a polynomial time algorithm, for the (easier) membership problem, for 2-generated abelian linear groups. Furthermore, we provide a polynomial-sized encoding for the set of all solutions.>