Campus Units
Computer Science, Mathematics
Document Type
Article
Publication Version
Accepted Manuscript
Publication Date
1-6-2002
Journal or Book Title
Theoretical Computer Science
Volume
270
Issue
1-2
First Page
591
Last Page
608
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
This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.
Copyright Owner
Elsevier Science B.V.
Copyright Date
2002
Language
en
File Format
application/pdf
Recommended Citation
Bergman, Clifford and Slutzki, Giora, "Computational complexity of some problems involving congruences on algebras" (2002). Mathematics Publications. 221.
https://lib.dr.iastate.edu/math_pubs/221
Included in
Algebra Commons, Numerical Analysis and Scientific Computing Commons, Theory and Algorithms Commons
Comments
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.