Algebra Seminar talk
2026-06-19
Vishwesh Tiwari
Schaefer's Theorem
Abstract:
Constraint Satisfaction Problems (CSPs) form a broad framework encompassing many fundamental computational problems. For a fixed relational structure $B$, $\mathrm{CSP}(B)$ is the problem of deciding whether a finite input structure $A$ has a homomorphism to $B$ (equivalently, whether a given conjunction of atomic formulas is satisfiable in $B$). A central question is: when can a CSP be solved efficiently, and when is it computationally intractable? Schaefer’s Dichotomy Theorem gives a complete answer for Boolean CSPs, i.e., CSPs of structures with the two-element domain $\{0,1\}$. It states that every Boolean CSP either belongs to one of a small number of tractable classes and is solvable in polynomial time, or it is NP-complete. In this talk, we will introduce CSPs, discuss the role of polymorphisms in capturing tractability, and outline the main ideas behind Schaefer’s classification theorem.