Computational complexity of some problems involving congruences on algebras Bergman, Clifford Bergman, Clifford Slutzki, Giora
dc.contributor.department Computer Science
dc.contributor.department Mathematics 2020-03-18T00:24:45.000 2020-06-30T06:00:30Z 2020-06-30T06:00:30Z Tue Jan 01 00:00:00 UTC 2002 2002-01-06
dc.description.abstract <p>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.</p>
dc.description.comments <p>This is a manuscript of an article published as Bergman, Clifford, and Giora Slutzki. "Computational complexity of some problems involving congruences on algebras." <em>Theoretical Computer Science</em> 270, no. 1-2 (2002): 591-608. doi: <a href="" target="_blank" title="Persistent link using digital object identifier">10.1016/S0304-3975(01)00009-3</a>. Posted with permission.</p>
dc.format.mimetype application/pdf
dc.identifier archive/
dc.identifier.articleid 1224
dc.identifier.contextkey 16778406
dc.identifier.s3bucket isulib-bepress-aws-west
dc.identifier.submissionpath math_pubs/221
dc.language.iso en
dc.source.bitstream archive/|||Fri Jan 14 22:42:15 UTC 2022
dc.source.uri 10.1016/S0304-3975(01)00009-3
dc.subject.disciplines Algebra
dc.subject.disciplines Numerical Analysis and Scientific Computing
dc.subject.disciplines Theory and Algorithms
dc.subject.keywords congruence
dc.subject.keywords simple algebra
dc.subject.keywords nondeterministic log-space
dc.subject.keywords graph accessibility
dc.title Computational complexity of some problems involving congruences on algebras
dc.type article
dc.type.genre article
dspace.entity.type Publication
relation.isAuthorOfPublication ff2cb02a-ee5f-4bb0-a939-4cdd406e54fa
relation.isOrgUnitOfPublication f7be4eb9-d1d0-4081-859b-b15cee251456
relation.isOrgUnitOfPublication 82295b2b-0f85-4929-9659-075c93e82c48
Original bundle
Now showing 1 - 1 of 1
241.81 KB
Adobe Portable Document Format