Thesis (Selection of subject)Thesis (Selection of subject)(version: 290)
Assignment details
   Login via CAS
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
Type of assignment: 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 proceeded defence: 18.09.2009
Reviewers: 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

 
Charles University | Information system of Charles University | http://www.cuni.cz/UKEN-329.html