Constraint satisfaction problems (CSP) are a large, important class of optimization problems studied in AI. Feder and Vardi gave a formal definition of CSP problems. They showed that all CSP problems are equivalent to a basic problem in database theory namely conjunctive query containment. It follows from Schaefer's dichotomy theorem on satisfiability problems that all CSP problems with a boolean target domain have a dichotomy in that each such problem is either NP complete or is in P, even though Ladner proved that if P is different from NP there is a dense hierarchy of problems strictly between P and NP. Feder and Vardi formulated a conjecture that this dichotomy holds for all CSP problems, not just boolean.
In March I was at a workshop in Barbados where Phokion Kolaitis
gave a week-long series of beautiful lectures on this topic.
I will give a survey of some of the basic results and problems
in what has now become a rich area of research at the
intersection of AI, databases, and theory.
Last modified 6 April 2003