Subjects

Your browser does not support JavaScript, or its support is disabled. Some features may not be available.

Introduction to complexity of CSP - NMAG563

Title:	Úvod do složitosti CSP
Guaranteed by:	Department of Algebra (32-KA)
Faculty:	Faculty of Mathematics and Physics
Actual:	from 2023
Semester:	winter
E-Credits:	3
Hours per week, examination:	winter s.:2/0, Ex [HT]
Capacity:	unlimited
Min. number of students:	unlimited
4EU+:	no
Virtual mobility / capacity:	no
State of the course:	taught
Language:	English, Czech
Teaching methods:	full-time

Guarantor:	Dmitrii Zhuk, Ph.D.
Teacher(s):	Dmitrii Zhuk, Ph.D.
Class:	M Mgr. MMIB M Mgr. MMIB > Povinně volitelné M Mgr. MSTR M Mgr. MSTR > Volitelné
Classification:	Mathematics > Algebra
Incompatibility :	NALG117
Interchangeability :	NALG117
Is interchangeable with:	NALG117

Opinion survey results Examination dates WS schedule Noticeboard

Annotation -

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. The course may not be taught every academic year.

Last update: Žemlička Jan, doc. Mgr. et Mgr., Ph.D. (14.05.2019)

Course completion requirements -

Students have to pass exam. The requirements for the exam correspond to what has been done during lectures.

Last update: Žemlička Jan, doc. Mgr. et Mgr., Ph.D. (28.10.2019)

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 (14.05.2013)

Requirements to the exam -

Solving problems during semester.

Last update: Žemlička Jan, doc. Mgr. et Mgr., Ph.D. (28.10.2019)

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 (14.05.2013)