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 field.

If interested, please enter your name and details in one of the participant lists:
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 themenspezifisch einzulesen.

Vorbesprechung vor Beginn des WS, wird durch Aushang angekündigt