a Department of Mathematics, Iowa State University, Ames, IA 50011-2066, USA
b Department of Computer Science, Iowa State University, Ames, IA 50011, USA
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.