Constraint Satisfaction, Complexity, and Logic
Phokion G. Kolaitis
Computer Science Department
University of California, Santa Cruz
Santa Cruz, CA 95064, USA
(kolaitis@cs.ucsc.edu)
phone: 831-459-4768
fax: 831-459-4829
http://www.cs.ucsc.edu/~kolaitis
Prerequisites: (1) Familiarity with the basic concepts of first-order logic
and second-order logic.
(2) Familiarity with the basic concepts and working knowledge of
the main results in computational complexity, especially
polynomial time computability and NP-completeness.
Summary: Constraint satisfaction problems constitute a broad
class of algorithmic problems that arise naturally
in several different areas of computer science,
artificial intelligence, and linguistics.
The aim of this course is to present an overview
of results in constraint satisfaction with emphasis
on the computational complexity of constraint satisfaction
problems and on the connections of this area of research
with logic and database theory.
Course Outline (Tentative): Lecture 1: Introduction to constraint satisfaction
problems (CSP); examples and formal definition of CSP;
CSP as the homomorphism problem; uniform and non-uniform CSP;
CSP and monadic second-order logic;
Lecture 2: Constraint satisfaction and database theory;
CSP and the relational join evaluation problem;
CSP and the conjunctive query containment problem.
Lecture 3: Complexity of uniform and non-uniform
CSP; Schaefer's dichotomy theory for the complexity
of Boolean non-uniform CSP; the Feder-Vardi dichotomy
conjecture for the complexit of non-uniform CSP.
Lecture 4: The pursuit of tractable cases of CSP - Part I:
Datalog, pebble games and CSP; consistency properties and CSP.
Lecture 5: The pursuit of tractable cases of CSP - Part II:
induced width, bounded tree-width and CSP.
Course Notes:
Course Reader
Back to course listing.