Computational complexity of some problems involving congruences on algebras
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.
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.