Seminar: Constraint Satisfaction Problems (CSP)
Constraint Satisfaction Problem (CSP) delineates a class of
decision problems with wide ranginging applications. The
traditional view (in artificial intelligence) regards
these problems as variable assignment problems under
given constraints (hence the name CSP); virtually the same problem
is known in database theory in connection with unions
of conjunctive queries.
In the more recent development of the CSP,
however, the interpretation as homomorphism problems has provided a
mathematically unified view. This view is also at the root of a systematic
study and classification of subproblems according to their complexity.
The general instance of this homomorphism problem is the following:
given two finite relational structures A and B,
decide whether there is a homomorphism from A to B - evidently
an NP decison issue. Moreover, important NP-complete
problems like 3-colourability, can be seen as subproblems of the
homomorphism problem (in this case: fix B to be a triangle).
Other subproblems are known to be plynomial time tractable. Many natural subproblems have been classified as NP-complete or else as tractable, and
the major conjecture in the area is that there is indeed a dichotomy
of this kind, or that intermediate complexity levels do not occur.
In the seminar we shall read a number of survey articles and original papers
dealing with the analysis of CSP, and in particular with key advances
towards the understanding of the dichotomy phenomenon. Methods from logic
and algorithmic aspects of (finite) model theory on the one hand, and
from universal algebra on the other hand, have greatly contributed to this
If interested, please enter your name and details in one of the
in the entrance to the second floor, maths building
or next to my office, room 207, maths building
Voraussetzungen: Grundkenntnisse in Logik, allgemeiner Algebra,
und/oder theoretischer Informatik, bzw. die Bereitschaft, sich
Vorbesprechung vor Beginn des WS, wird durch Aushang angekündigt