Constraint Satisfaction Problem and Universal Algebra

• Thesis title in Czech: Problém splnitelnosti omezení a univerzální algebra
• Thesis title in English: Constraint Satisfaction Problem and Universal Algebra
• Key words: CSP, univerzální algebra, orientovaný graf, absorpce
• English key words: CSP, universal algebra, digraph, absorption
• Academic year of topic announcement: 2009/2010
• Thesis type: dissertation
• Thesis language: angličtina
• Department: Department of Algebra (32-KA)
• Supervisor: doc. Mgr. Libor Barto, Ph.D.
• Author: hidden - assigned and confirmed by the Study Dept.
• Date of registration: 29.09.2009
• Date of assignment: 03.11.2009
• Date and time of defence: 20.06.2013 13:30
• Date of electronic submission: 28.03.2013
• Date of submission of printed version: 28.03.2013
• Date of proceeded defence: 20.06.2013
• Opponents: doc. Mgr. Pavel Růžička, Ph.D.

Guidelines

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.

References

[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.