Computational complexity of some problems involving congruences on algebras

dc.contributor.author Bergman, Clifford
dc.contributor.author Bergman, Clifford
dc.contributor.author Slutzki, Giora
dc.contributor.department Computer Science
dc.contributor.department Mathematics
dc.date 2020-03-18T00:24:45.000
dc.date.accessioned 2020-06-30T06:00:30Z
dc.date.available 2020-06-30T06:00:30Z
dc.date.copyright Tue Jan 01 00:00:00 UTC 2002
dc.date.issued 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="https://doi.org/10.1016/S0304-3975(01)00009-3" 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/lib.dr.iastate.edu/math_pubs/221/
dc.identifier.articleid 1224
dc.identifier.contextkey 16778406
dc.identifier.s3bucket isulib-bepress-aws-west
dc.identifier.submissionpath math_pubs/221
dc.identifier.uri https://dr.lib.iastate.edu/handle/20.500.12876/54613
dc.language.iso en
dc.source.bitstream archive/lib.dr.iastate.edu/math_pubs/221/2002_Bergman_Computational_ComplexitySomeManuscript.pdf|||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
File
Original bundle
Now showing 1 - 1 of 1
Name:
2002_Bergman_Computational_ComplexitySomeManuscript.pdf
Size:
241.81 KB
Format:
Adobe Portable Document Format
Description:
Collections