Computer Science, Mathematics
Journal or Book Title
Theoretical Computer Science
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 License.
Elsevier Science B.V.
Bergman, Clifford and Slutzki, Giora, "Computational complexity of some problems involving congruences on algebras" (2002). Mathematics Publications. 221.