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
Generalizing CSP-related results to infinite algebras
Název práce v češtině: Zobecňování výsledků týkajících se problému splnitelnosti podmínek na nekonečné algebry
Název v anglickém jazyce: Generalizing CSP-related results to infinite algebras
Klíčová slova: problém splnitelnosti podmínek, Maltsevské podmínky, smyčková lemmata
Klíčová slova anglicky: constraint satisfaction problem, Maltsev conditions, loop lemmata
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í: 25.09.2015
Datum zadání: 25.09.2015
Datum potvrzení stud. oddělením: 05.10.2015
Datum a čas obhajoby: 05.06.2019 13:00
Datum odevzdání elektronické podoby:27.02.2019
Datum odevzdání tištěné podoby:01.03.2019
Datum proběhlé obhajoby: 05.06.2019
Oponenti: Dmitrii Zhuk, Ph.D.
  Michael Pinsker, dipl. ing.
 
 
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, 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).
Seznam odborné literatury
[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.
 
Univerzita Karlova | Informační systém UK