Témata prací (Výběr práce)Témata prací (Výběr práce)(verze: 290)
Detail práce
   Přihlásit přes CAS
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
 
Univerzita Karlova | Informační systém UK