Article
Computational complexity of some problems involving congruences on algebras
Theoretical Computer Science
Document Type
Article
Disciplines
Publication Version
Accepted Manuscript
Publication Date
1-6-2002
DOI
10.1016/S0304-3975(01)00009-3
Abstract
We prove that several problems concerning congruences on algebras are complete for nondeterministic log-space. These problems are: determining the congruence on a given algebra generated by a set of pairs, and determining whether a given algebra is simple or subdirectly irreducible. We also consider the problem of determining the smallest fully invariant congruence on a given algebra containing a given set of pairs. We prove that this problem is complete for nondeterministic polynomial time.
Creative Commons License
Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International
Copyright Owner
Elsevier Science B.V.
Copyright Date
2002
Language
en
File Format
application/pdf
Citation Information
Clifford Bergman and Giora Slutzki. "Computational complexity of some problems involving congruences on algebras" Theoretical Computer Science Vol. 270 Iss. 1-2 (2002) p. 591 - 608 Available at: http://works.bepress.com/clifford_bergman/21/
This is a manuscript of an article published as Bergman, Clifford, and Giora Slutzki. "Computational complexity of some problems involving congruences on algebras." Theoretical Computer Science 270, no. 1-2 (2002): 591-608. doi: 10.1016/S0304-3975(01)00009-3. Posted with permission.