Campus Units

Computer Science, Mathematics

Document Type

Article

Publication Version

Accepted Manuscript

Publication Date

2002

Journal or Book Title

International Journal of Algebra and Computation

Volume

12

Issue

5

First Page

719

Last Page

735

DOI

10.1142/S0218196702001127

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.

Copyright Owner

World Scientific Publishing Company

Language

en

File Format

application/pdf

Published Version

Share

COinS