The constraint satisfaction problem (CSP) provides a framework in which it is possible to express, in a natural way, many
combinatorial problems encountered in artificial intelligence and computer science. In many cases effective algorithms exist
to solve such a problem, and in others (such as 3SAT) we can show it to be NP-complete. It is conjectured that every CSP
is either in P or NP-complete, which is the so called dichotomy conjecture. In the course, we will study the mathematics of
CSP and focus on algebraic methods.
Last update: T_KA (19.05.2009)
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. V mnoha případech existují efektivní algoritmy pro řešení
tohoto problému, v jiných (například 3SAT) lze ukázat jeho NP-úplnost. Takzvaná dichotomická hypotéza říká, že každý
CSP je buď polynomiálně řešitelný, nebo NP-úplný. V přednášce se zaměříme na matematické aspekty CSP, zejména na
algebraický přístup k řešení dichotomické hypotézy.
Last update: T_KA (19.05.2009)
Literature -
[1] A. Bulatov, A. Krokhin, P. Jeavons: Constraint satisfaction problems and finite algebras. In: Proc. 27th International Colloquium on Automata, Languages and Programming, ICALP'00. Volume 1853 of LNCS, Springer-Verlag (2000) 272-282.
[2] V. Dalmau: Generalized majority-minority operations are tractable. In Proceedings 20th IEEE Symposium on Logic in Computer Science, (LICS 2005),438-447.
[3] T. Feder, M.Y. Vardi: The computational structure of monotone monadic SNP and constraint satisfaction: a study through Datalog and group theory. SIAM J. Computing, 28 (1), 1998, 57-104.
[4] B. Larose, L. Zádori: Bounded width problems and algebras. Algebra Universalis 56 (3-4), 2007, 439-466.
[5] T. J. Schaefer: The complexity of satisfiability problems, in Proc. 10th ACM Symp. on Theory of Computing, ACM, New York, 1978, 216-226.
Last update: T_KA (19.05.2009)
[1] A. Bulatov, A. Krokhin, P. Jeavons: Constraint satisfaction problems and finite algebras. In: Proc. 27th International Colloquium on Automata, Languages and Programming, ICALP'00. Volume 1853 of LNCS, Springer-Verlag (2000) 272-282.
[2] V. Dalmau: Generalized majority-minority operations are tractable. In Proceedings 20th IEEE Symposium on Logic in Computer Science, (LICS 2005),438-447.
[3] T. Feder, M.Y. Vardi: The computational structure of monotone monadic SNP and constraint satisfaction: a study through Datalog and group theory. SIAM J. Computing, 28 (1), 1998, 57-104.
[4] B. Larose, L. Zádori: Bounded width problems and algebras. Algebra Universalis 56 (3-4), 2007, 439-466.
[5] T. J. Schaefer: The complexity of satisfiability problems, in Proc. 10th ACM Symp. on Theory of Computing, ACM, New York, 1978, 216-226.
Last update: T_KA (19.05.2009)
Syllabus -
1. Definition of CSP, its equivalent forms, basic notions and properties
2. Polymorphisms, algebraic reductions
3. Bounded width problems
4. Schaefer's dichotomy theorem for boolean CSPs
5. Maltsev CSPs
Last update: T_KA (19.05.2009)
1. Definice CSP, ekvivalentní přístupy, základní pojmy a vlastnosti
2. Polymorfismy, algebraické redukce
3. Problémy konečné šířky
4. Schaeferova věta o dichotomii pro booleovská CSP
