Algebraický přístup k CSP

• Thesis title in Czech: Algebraický přístup k CSP
• Thesis title in English: Algebraic Approach to CSP
• Academic year of topic announcement: 2008/2009
• Thesis type: Bachelor's thesis
• Thesis language: čeština
• Department: Department of Algebra (32-KA)
• Supervisor: doc. Mgr. Pavel Růžička, Ph.D.
• Author: hidden - assigned and confirmed by the Study Dept.
• Date of registration: 22.10.2008
• Date of assignment: 22.10.2008
• Date and time of defence: 18.09.2009 00:00
• Date of electronic submission: 18.09.2009
• Date of proceeded defence: 18.09.2009
• Opponents: doc. Mgr. Libor Barto, Ph.D.

Guidelines

Jedna z možných formulací CSP (the Constraint Satisfaction Problem) je tato: Jsou dány dvě konečné relační struktury A,B stejného typu. Jak složité je rozhodnout zda existuje homomorfismus z A do B? Speciálně je možné položit tento problém v případě, kdy B fixujeme a A může být libovolné. Ukazuje se, že tato složitost závisí pouze na algebře polymorfismů B. Je otázkou, které typy algeber zaručí polynomiální složitost, které zaručí to, že CSP je NP-úplný a zda platí dichotomie, tedy zda polynomiální složitost a NP-úplnost jsou jediné možnosti.

Cílem práce je zpracovat dosavadní částečné výsledky.

References

1. P.G. Jeavons. On the algebraic structure of combinatorial problems. Theoretical Computer Science, 200:185?204, 1998

2. Andrei A. Bulatov, Andrei A. Krokhin, Peter Jeavons In: Proceedings of the 27th International Coll. on Automata, Languages and Programming- ICALP?00, LNCS 1853