Classifying the Complexity of SAT and CSP: Are we there yet?
Talkat 50 Years of Satisfiability: The Centrality of SAT in the Theory of Computing · 2021-02-11..05-13
summary
Classifies when finite-domain SAT/CSP are tractable versus NP-complete by pinning complexity to actual algebraic symmetries: polymorphisms control gadget reductions and trivial polymorphisms imply NP-completeness while nontrivial ones give algorithms. Key claims: the Feder–Vardi dichotomy becomes an algebraic dichotomy proved 2017 (Bulatov and Zhuk); main algorithms are local consistency and the few-subpowers/recursive reductions; promise CSPs (PCSP) generalize CSP and force infinite relaxations (LP/affine) and topology in some cases. Concrete gaps remain: 3-colorable→find coloring needs ≈N^(1/5) colors best known, NP-hard to find 5-coloring.
AI-written summary · about
chapters (17)
- 0:00Intro
- 0:35GENERALIZED SATISFIABILITY
- 2:03Schaefer's dichotomy
- 8:24The Constraint Satisfaction Problem (CSP)
- 11:27The Feder-Vardi CSP Dichotomy Conjecture
- 19:11The insights of Jeavons et al.
- 23:25General theory of gadget reductions
- 27:11Trivial and non-trivial symmetries
- 34:46Structural universal algebra
- 38:14Two main algorithmic ideas for CSP
- 40:09The Bulatov-Zhuk CSP Dichotomy Theorem
- 44:17Approximate graph colouring
- 49:42Promise CSP (PCSP)
- 51:06Boolean PCSP
- 52:54Extended theory of gadget reductions
- 53:16Promise graph homomorphisms
- 55:31Summary