Computational complexity of generators and nongenerators in algebra
Date
Authors
Major Professor
Advisor
Committee Member
Journal Title
Journal ISSN
Volume Title
Publisher
Authors
Research Projects
Organizational Units
Journal Issue
Is Version Of
Versions
Series
Department
Abstract
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).
Comments
This is a manuscript of an article published as Bergman, Clifford, and Giora Slutzki. "Computational complexity of generators and nongenerators in algebra." International Journal of Algebra and Computation 12, no. 05 (2002): 719-735. doi: 10.1142/S0218196702001127. Posted with permission.