## Paper: Computational Complexity of Some Problems Involving Congruences on Algebras (at LICS 2000)

**Clifford Bergman Giora Slutzki**

### 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.

### BibTeX

@InProceedings{BergmanSlutzki-ComputationalComple, author = {Clifford Bergman and Giora Slutzki}, title = {Computational Complexity of Some Problems Involving Congruences on Algebras}, booktitle = {Proceedings of the Fifteenth Annual IEEE Symposium on Logic in Computer Science (LICS 2000)}, year = {2000}, month = {June}, pages = {168--174}, location = {Santa Barbara, CA, USA}, publisher = {IEEE Computer Society Press} }