2003 Barbados Workshop on Computational Complexity -- Outline

Workshop Outline 2003

  1. Examples and formal definition of constraint satisfaction problems (CSP); CSP and the homomorphism problem; uniform and non-uniform CSP.
  2. CSP and database theory: connections with the conjunctive query evaluation problem and the conjunctive query containment problem.
  3. Computational complexity of CSP
  4. The pursuit of tractable cases of CSP: