The Complexity of the A B C Problem
Jin‐Yi Cai, Richard J. Lipton, Yechezkel Zalcstein · SIAM Journal on Computing · 2000
We present a deterministic polynomial-time algorithm for the A B C 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.