Many real-life and combinatorial problems can be naturally expressed as aconstraint satisfaction problem (CSP), making it a
universal, easy to understand declarative programming language. In many cases effective algorithms exist to solve such a
problem, and in others (such as 3SAT) we can show it to beNP-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 themathematics of CSP and focus on
graph-theoretic and algebraic methods throughreading a series of research papers.
Last update: T_KA (20.05.2009)
Přednáška se zabývá vybranými tématy problému splnitelnosti omezení (the Constraint Satisfaction Problem, CSP).
Literature -
Last update: T_KA (11.04.2007)
[1] J. Berman, P. Idziak, P. Markovic, R. McKenzie, M. Valeriote and R. Willard, Varieties with few subalgebras of powers, preprint.
[2] B. A. Davey, L. Heindorf and R. McKenzie, Near unanimity: an obstacle to general duality theory, Algebra Universalis 33 (1995), no. 3, 428-439.
[3] P. Idziak, P. Markovic, R. McKenzie, M. Valeriote and R. Willard, Tractability and learnability arising from algebras with few subpowers, to appear in Proceedings of the 22nd Annual IEEE Symposium on Logic in Computer Science (LICS'07), July 10-14, Wroclaw, Poland.
[4] E. Kiss and M. Valeriote, On tractability and congruence distributivity (extended abstract), in Proceedings of the 21st Annual IEEE Symposium on Logic in Computer Science (LICS'06), IEEE, 221-230.
[5] M. Maroti, The existence of a near-unanimity term in a finite algebra is decidable, preprint.
[6] M. Maroti and R. McKenzie, Existence theorems for weakly symmetric operations, preprint.
[7] M. Nickodemus, An extension of Pontryagin duality, preprint.
Last update: T_KA (11.04.2007)
[1] J. Berman, P. Idziak, P. Markovic, R. McKenzie, M. Valeriote and R. Willard, Varieties with few subalgebras of powers, preprint.
[2] B. A. Davey, L. Heindorf and R. McKenzie, Near unanimity: an obstacle to general duality theory, Algebra Universalis 33 (1995), no. 3, 428-439.
[3] P. Idziak, P. Markovic, R. McKenzie, M. Valeriote and R. Willard, Tractability and learnability arising from algebras with few subpowers, to appear in Proceedings of the 22nd Annual IEEE Symposium on Logic in Computer Science (LICS'07), July 10-14, Wroclaw, Poland.
[4] E. Kiss and M. Valeriote, On tractability and congruence distributivity (extended abstract), in Proceedings of the 21st Annual IEEE Symposium on Logic in Computer Science (LICS'06), IEEE, 221-230.
[5] M. Maroti, The existence of a near-unanimity term in a finite algebra is decidable, preprint.
[6] M. Maroti and R. McKenzie, Existence theorems for weakly symmetric operations, preprint.
[7] M. Nickodemus, An extension of Pontryagin duality, preprint.
Syllabus -
Last update: T_KA (10.04.2007)
This course is intended as a continuation of the course which will betaught by Miklos Maroti in Fall 2007. The following new results willbe presented:
the new, improved characterization of finitely generated varietiesomitting type 1 (i. e. those for which the Dichotomy Conjecture saysthe CSP should be tractable), proved by Maroti and McKenzie in [6],
the proof of bounded width for the finite idempotent algebras invarieties with Jonsson width 3 by Kiss and Valeriote [4], and
the proof that the finite idempotent algebras with few subpowers are tractable [1] [3].
Last update: T_KA (10.04.2007)
This course is intended as a continuation of the course which will betaught by Miklos Maroti in Fall 2007. The following new results willbe presented:
the new, improved characterization of finitely generated varietiesomitting type 1 (i. e. those for which the Dichotomy Conjecture saysthe CSP should be tractable), proved by Maroti and McKenzie in [6],
the proof of bounded width for the finite idempotent algebras invarieties with Jonsson width 3 by Kiss and Valeriote [4], and
the proof that the finite idempotent algebras with few subpowers are tractable [1] [3].
