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
Problém splnitelnosti omezení a univerzální algebra
Název práce v češtině:
Název v anglickém jazyce: Constraint Satisfaction Problem and Universal Algebra
Akademický rok vypsání: 2008/2009
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:
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.
Předběžná náplň práce
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.
Předběžná náplň práce v anglickém jazyce
The Constraint Satisfaction Problem (CSP) provides a common framework for many combinatorial problems in artificial intelligence and computer science. An instance of CSP consists of variables and constraints and the aim is to determine whether variables can be evaluated in such a way that all the constraints are satisfied. One of the most studied forms of CSP are non-uniform CSPs, where constraints are taken from a fixed finite set called the template. The most famous open question in this field is the Dichotomy Conjecture of Feder and Vardi, postulating that every non-uniform CSP is solvable in polynomial time or NP-complete.

The Dichotomy Conjecture has proved to be a challenging question and advances using standard methods were slow. A breakthrough in the development occurred when Jeavons, Cohen and Gyssens announced an algebraic approach to the problem. Their work, refined later by Bulatov, Jeavons and Krokhin, showed that the complexity of a non-uniform CSP is fully determined by a set of operations - the polymorphisms of the template. This tight connection between the complexity of CSP and universal algebra made it possible to use strong universal algebraic tools (namely the Tame Congruence Theory of Hobby and McKenzie) to study CSP, and led to results unreachable before.

The thesis can concentrate on (special cases of) The Dichotomy Conjecture, the algebraic tools for CSP, finer complexity and descriptive classification of CSP (Datalog, Linear Datalog, Symmetric Datalog), global tractability or approximability questions.
 
Univerzita Karlova | Informační systém UK