COMPUTATIONAL COMPLEXITY OF GENERATORS AND NONGENERATORS IN ALGEBRA
COMPUTATIONAL COMPLEXITY OF GENERATORS AND NONGENERATORS IN ALGEBRA
We discuss the computational complexity of several problems concerning subsets of an algebraic structure that generate the structure. We show that the problem of determining whether a given subset X generates an algebra A is P-complete, while determining the size of the smallest generating set is NP-complete. We also consider …