Computational complexity of generators and nongenerators in algebra

Date
2002-01-01
Authors
Bergman, Clifford
Slutzki, Giora
Bergman, Clifford
Journal Title
Journal ISSN
Volume Title
Publisher
Source URI
Altmetrics
Authors
Research Projects
Organizational Units
Computer Science
Organizational Unit
Mathematics
Organizational Unit
Journal Issue
Series
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).

Description
<p>This is a manuscript of an article published as Bergman, Clifford, and Giora Slutzki. "Computational complexity of generators and nongenerators in algebra." <em>International Journal of Algebra and Computation</em> 12, no. 05 (2002): 719-735. doi: <a href="https://doi.org/10.1142/S0218196702001127">10.1142/S0218196702001127</a>. Posted with permission.</p>
Keywords
Citation
Collections