An Algebraic Approach to the Constraint Satisfaction Problem
| Thesis title in Czech: | |
|---|---|
| Thesis title in English: | An Algebraic Approach to the Constraint Satisfaction Problem |
| Academic year of topic announcement: | 2007/2008 |
| Thesis type: | diploma thesis |
| Thesis language: | angličtina |
| Department: | Department of Algebra (32-KA) |
| Supervisor: | doc. Mgr. Libor Barto, Ph.D. |
| Author: |
| Guidelines |
| Úkolem práce je shrnout a prohloubit poznatky o dichotomii pro CSP (Constraint Satisfaction Problem) se zaměřením na algebraický přístup k tomuto problému.
Pro danou relacni strukturu R je CSP(R) nasledujici problem: VSTUP: Relacni struktura S stejneho typu jako R VYSTUP: ANO, pokud existuje homomorfismus S->R; NE, jinak Feder a Vardi [1] vyslovili domnenku, ze CSP(R) je, pro libovolnou strukturu R, bud polynomialne resitelny, nebo NP-uplny. Tento problem je otevreny, nicmene je znamo mnoho castecnych vysledku. Prulomovym krokem byl preklad do univerzalni algebry (viz [3]), jehoz uzitim byla otazka zodpovezena kladne napr. pro triprvkove relacni struktury [2], hladke digrafy [4], aj. |
| References |
| [1] T. Feder, M. Vardi, The computational structure of monotone monadic SNP and constraint
satisfaction: a study through Datalog and group theory. SIAM J. Comput. 28 (1999), no. 1, 57–104. [2] A. Bulatov: A dichotomy theorem for constraints on a three element set. In: FOCS’02, 2002, 649–658. [3] A. Bulatov, P. Jeavons, A. Krokhin, Classifying the complexity of constraints using finite algebras. SIAM J. Comput. 34 (2005), no. 3, 720–742. [4] L. Barto, M. Kozik, T.Niven, CSP dichotomy holds for digraphs with no sources and no sinks (a positive answer to the conjecture of Bang-Jensen and Hell), manuscript |