Generalizing CSP-related results to infinite algebras
| Thesis title in Czech: | Zobecňování výsledků týkajících se problému splnitelnosti podmínek na nekonečné algebry |
|---|---|
| Thesis title in English: | Generalizing CSP-related results to infinite algebras |
| Key words: | problém splnitelnosti podmínek, Maltsevské podmínky, smyčková lemmata |
| English key words: | constraint satisfaction problem, Maltsev conditions, loop lemmata |
| 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: | 25.09.2015 |
| Date of assignment: | 25.09.2015 |
| Confirmed by Study dept. on: | 05.10.2015 |
| Date and time of defence: | 05.06.2019 13:00 |
| Date of electronic submission: | 27.02.2019 |
| Date of submission of printed version: | 01.03.2019 |
| Date of proceeded defence: | 05.06.2019 |
| Opponents: | Dmitrii Zhuk, Ph.D. |
| Michael Pinsker, dipl. ing. | |
| 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, strukturní popis polynomiálních případů ve speciálních strukturách (digrafy), algebraické nástroje pro CSP, jemnější složitostní a deskriptivní klasifikaci CSP (Datalog, lineární Datalog, symetrický Datalog). |
| References |
| [1] Libor Barto, Marcin Kozik. Constraint Satisfaction Problems of Bounded Width. FOCS 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] Libor Barto, Marcin Kozik. Cyclic terms in algebraic approach to CSP. Manuscript. [4] 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. [5] Andrei Bulatov and Víctor Dalmau. A simple algorithm for Mal'tsev constraints. SIAM J. Comput., 36(1):16?27, 2006. [6] Andrei Bulatov, Peter Jeavons, and Andrei Krokhin. Classifying the complexity of constraints using finite algebras. SIAM J. Comput., 34(3):720-742, 2005. [7] 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. [8] Andrei A. Bulatov. A dichotomy theorem for constraint satisfaction problems on a 3-element set. J. ACM, 53(1):66-120, 2006. [9] Andrei A. Bulatov, Andrei A. Krokhin, and Benoit Larose. Dualities for constraint satisfaction problems (a survey paper). LNCS 5250 (to appear), 2008. [10] 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. [11] David Hobby and Ralph McKenzie, The Structure of Finite Algebras, Memoirs of the American Mathematical Society, No. 76, American Mathematical Society, Providence, RI, 1988. [12] Benoit Larose and László Zádori. Bounded width problems and algebras. Algebra Universalis, 56(3-4):439-466, 2007. [13] Miklós Maróti and Ralph McKenzie. Existence theorems for weakly symmetric operations. Algebra Universalis, 59(3-4):463-489, 2008. |