Computational complexity of some problems involving congruences on algebras
| 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
1 - 1 of 1
No Thumbnail Available
- Name:
- 2002_Bergman_Computational_ComplexitySomeManuscript.pdf
- Size:
- 241.81 KB
- Format:
- Adobe Portable Document Format
- Description: