Computational complexity of some problems involving congruences on algebras

Date
2002-01-06
Authors
Bergman, Clifford
Slutzki, Giora
Journal Title
Journal ISSN
Volume Title
Publisher
Altmetrics
Authors
Research Projects
Organizational Units
Computer Science
Organizational Unit
Mathematics
Organizational Unit
Journal Issue
Series
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.

Description

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.

Keywords
congruence, simple algebra, nondeterministic log-space, graph accessibility
Citation
DOI
Collections