Algebra complexity problems involving graph homomorphism, semigroups and the constraint satisfaction problem

✍ Scribed by Steve Seif; Csaba Szabó

• Publisher: Elsevier Science
• Year: 2003
• Tongue: English
• Weight: 130 KB
• Volume: 19
• Category: Article
• ISSN: 0885-064X
• DOI: 10.1016/s0885-064x(02)00027-4

✦ Synopsis

In this paper, we connect the constraint satisfaction problem with other complexity problems, like the polynomial equivalence problem for combinatorial 0-simple semigroups, the graph retraction problem and the geometry problem. We show that every constraint satisfaction problem is polynomially equivalent to an easily formulated algebra complexity problem. As an application we prove that the polynomial equivalence problem (word problem) for the 2 Â 2 matrices over the two element field is co-NP-complete.