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
Constraint Satisfaction Problem and Universal Algebra
Název práce v češtině: Problém splnitelnosti omezení a univerzální algebra
Název v anglickém jazyce: Constraint Satisfaction Problem and Universal Algebra
Klíčová slova: CSP, univerzální algebra, orientovaný graf, absorpce
Klíčová slova anglicky: CSP, universal algebra, digraph, absorption
Akademický rok vypsání: 2009/2010
Typ práce: disertační práce
Jazyk práce: angličtina
Ústav: Katedra algebry (32-KA)
Vedoucí / školitel: doc. Mgr. Libor Barto, Ph.D.
Řešitel: skrytý - zadáno a potvrzeno stud. odd.
Datum přihlášení: 29.09.2009
Datum zadání: 03.11.2009
Datum a čas obhajoby: 20.06.2013 13:30
Datum odevzdání elektronické podoby:28.03.2013
Datum odevzdání tištěné podoby:28.03.2013
Datum proběhlé obhajoby: 20.06.2013
Oponenti: doc. Mgr. Pavel Růžička, Ph.D.
  prof. Matt Valeriote
 
 
Zásady pro vypracování
Problém splnitelnosti omezení (the Constraint Satisfaction Problem, CSP) poskytuje společný rámec pro studium mnoha kombinatorických problémů v umělé inteligenci a informatice. Instance CSP sestává z proměnných a omezení, cílem je rozhodnout, zda lze proměnné ohodnotit tak, aby všechna omezení byla splněna. Jedny z nejstudovanějších forem CSP jsou neuniformní CSP, kde omezení jsou vybírány z předem dané konečné množiny, tzv. šablony. Nejslavnější otevřenou otázkou je dichotomická hypotéza Federa a Vardiho, která říká, že neuniformní CSP je NP úplné nebo řešitelné v polynomiálním čase.

Dichotomická hypotéza se ukázala být těžkým problémem a pokrok užitím standardních metod byl pomalý. Průlomem byl Jeavonsův, Cohenův a Gyssensův objev algebraického přístupu k problému. Jejich práce, později zjemněná Bulatovem, Jeavonsem a Krokhinem, ukázala, že složitost neuniformního CSP je plně určená jistou množinou operací - polymorfismy šablony. Tento úzký vztah mezi složitostí CSP a univerzální algebrou umožnil užití silných univerzálně algebraických nástrojů (zejména teorie krotkých kongruencí Hobbyho a McKenzieho) ke studiu CSP a vedla k dříve nedosažitelným výsledkům.

Disertační práce se může zaměřit na (speciální případy) dichotomické hypotézy, algebraické nástroje pro CSP, jemnější složitostní a deskriptivní klasifikaci CSP (Datalog, lineární Datalog, symetrický Datalog), globální polynomiální řešitelností nebo otázky aproximability.
Seznam odborné literatury
[1] Libor Barto and Marcin Kozik. Constraint Satisfaction Problems of Bounded Width. manuscript, 2009.
[2] Libor Barto, Marcin Kozik, and Todd Niven. Graphs, polymorphisms and the complexity of homomorphism problems. In STOC'08: Proceedings of the 40th annual ACM symposium on Theory of computing, pages 789-796, New York, NY, USA, 2008. ACM. 10
[3] Joel Berman, Pawel Idziak, Petar Markovic, Ralph McKenzie, Matthew Valeriote, and Ross Willard. Varieties with few subalgebras of powers. Trans. Amer. Math. Soc. (to appear), 2006.
[4] Andrei Bulatov and Víctor Dalmau. A simple algorithm for Mal'tsev constraints. SIAM J. Comput., 36(1):16?27, 2006.
[5] Andrei Bulatov, Peter Jeavons, and Andrei Krokhin. Classifying the complexity of constraints using finite algebras. SIAM J. Comput., 34(3):720-742, 2005.
[6] Andrei A. Bulatov. Tractable conservative constraint satisfaction problems. In LICS ?03: Proceedings of the 18th Annual IEEE Symposium on Logic in Computer Science, page 321, Washington, DC, USA, 2003. IEEE Computer Society.
[7] Andrei A. Bulatov. A dichotomy theorem for constraint satisfaction problems on a 3-element set. J. ACM, 53(1):66-120, 2006.
[8] Andrei A. Bulatov, Andrei A. Krokhin, and Benoit Larose. Dualities for constraint satisfaction problems (a survey paper). LNCS 5250 (to appear), 2008.
[9] Tomás Feder and Moshe Y. Vardi. The computational structure of monotone monadic SNP and constraint satisfaction: a study through Datalog and group theory. SIAM J. Comput., 28(1):57-104, 1999.
[10] David Hobby and Ralph McKenzie, The Structure of Finite Algebras, Memoirs of the American Mathematical Society, No. 76, American Mathematical Society, Providence, RI, 1988.
[11] Benoit Larose and László Zádori. Bounded width problems and algebras. Algebra Universalis, 56(3-4):439-466, 2007.
[12] Miklós Maróti and Ralph McKenzie. Existence theorems for weakly symmetric operations. Algebra Universalis, 59(3-4):463-489, 2008.
 
Univerzita Karlova | Informační systém UK