Title :
The complexity of the membership problem for 2-generated commutative semigroups of rational matrices
Author :
Cai, Jin-Yi ; Lipton, Richard J. ; Zalcstein, Yechezkel
Author_Institution :
Dept. of Comput. Sci., State Univ. of New York, Buffalo, NY, USA
Abstract :
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
Keywords :
computational complexity; deterministic algorithms; encoding; matrix algebra; 2-generated abelian linear groups; 2-generated commutative semigroups; ABC problem; algebraic number field; deterministic polynomial-time algorithm; membership problem complexity; polynomial time algorithm; polynomial-sized encoding; rational matrices; Computer science; Encoding; Galois fields; Physics; Polynomials; Testing;
Conference_Titel :
Foundations of Computer Science, 1994 Proceedings., 35th Annual Symposium on
Conference_Location :
Santa Fe, NM
Print_ISBN :
0-8186-6580-7
DOI :
10.1109/SFCS.1994.365699
