Computer Science, Mathematics
Journal or Book Title
International Journal of Algebra and Computation
We discuss the computational complexity of several prob- lems 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 several questions related to the Frattini subuniverse, Φ(A), of an algebra A. We show that the membership problem for Φ(A) is co-NP-complete, while the membership problems for Φ(Φ(A)), Φ(Φ(Φ(A))),... all lie in the class P (NP).
World Scientific Publishing Company
Bergman, Clifford and Slutzki, Giora, "Computational complexity of generators and nongenerators in algebra" (2002). Mathematics Publications. 222.