An Algebraic Approach to the Constraint Satisfaction Problem
Název práce v češtině: | |
---|---|
Název v anglickém jazyce: | An Algebraic Approach to the Constraint Satisfaction Problem |
Akademický rok vypsání: | 2007/2008 |
Typ práce: | diplomová práce |
Jazyk práce: | angličtina |
Ústav: | Katedra algebry (32-KA) |
Vedoucí / školitel: | doc. Mgr. Libor Barto, Ph.D. |
Řešitel: |
Zásady pro vypracování |
Ú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. |
Seznam odborné literatury |
[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 |