Opening Constraint Satisfaction Problems
Constraint Satisfaction Problems
- Length
- 32 min
- Level
- Undergraduate
- Recorded
- Carnegie Mellon University2020
Chapter 1 of 4: Terminology of two-satisfiability
Casts Max-Cut, 2-Sat, 3-Sat and graph coloring as CSPs, then traces Schaefer's theorem to the Dichotomy Theorem.
Constraint satisfaction problems (CSPs) consist of a domain, a set of allowed predicates, and constraints that apply those predicates to scopes of variables. O'Donnell builds the definition from the terminology of 2-Sat, then fits Max-Cut, 3-Sat and graph coloring into the same framework. He separates three tasks: deciding satisfiability, maximizing the fraction of satisfied constraints, and certifying an upper bound on the optimum. The complexity history runs from Schaefer's 1978 Boolean dichotomy and the 1993 Feder–Vardy conjecture to the algebraic conjecture of Bulatov, Jeavons and Krokhin. It ends with Bulatov's domain-size-3 case and the 2017 proofs by Bulatov and Zhuk. Lecture 20b of Carnegie Mellon's "CS Theory Toolkit" assumes P, NP-completeness and basic graph terms.
Constraint satisfaction problems (CSPs) consist of a domain, a set of allowed predicates, and constraints that apply those predicates to scopes of variables. O'Donnell builds the definition from the terminology of 2-Sat, then fits Max-Cut, 3-Sat and graph coloring into the same framework. He separates three tasks: deciding satisfiability, maximizing the fraction of satisfied constraints, and certifying an upper bound on the optimum. The complexity history runs from Schaefer's 1978 Boolean dichotomy and the 1993 Feder–Vardy conjecture to the algebraic conjecture of Bulatov, Jeavons and Krokhin. It ends with Bulatov's domain-size-3 case and the 2017 proofs by Bulatov and Zhuk. Lecture 20b of Carnegie Mellon's "CS Theory Toolkit" assumes P, NP-completeness and basic graph terms.

This lecture
Lecture 64 of 89 of A Theorist's Toolkit.
Choose a node to see how it connects to this lecture. What comes before is on the leftat the top. What comes after is on the rightat the bottom. The ring is what it teaches. People and places are above. Other lectures and books are below.
Press a chosen node again to open it.
Your comment is kept while you sign up.Sign in