2003 Barbados Workshop on Computational Complexity -- Outline
Workshop Outline 2003
- Examples and formal definition of constraint
satisfaction problems (CSP); CSP and
the homomorphism problem; uniform and non-uniform CSP.
- CSP and database theory: connections with
the conjunctive query evaluation problem and
the conjunctive query containment problem.
- Computational complexity of CSP
- Schaefer's dichotomy theory for the complexity of
Boolean non-uniform CSP;
- Feder-Vardi dichotomy conjecture for the complexity of
- The pursuit of tractable cases of CSP:
- Connections with universal algebra; closure properties
of constraints and the Galois connection.
- Datalog, existential k-pebble games and consistency properties
- Bounded treewidth and finite-variable logics.