Schaefer's Dichotomy Theorem - Modern Presentation

Modern Presentation

A modern, streamlined presentation of Schaefer's theorem is given in an expository paper by Hubie Chen. In modern terms, the problem SAT(S) is viewed as a constraint satisfaction problem over the Boolean domain. In this area, it is standard to denote the set of relations by Γ and the decision problem defined by Γ as CSP(Γ).

This modern understanding uses algebra, in particular, universal algebra. For Schaefer's dichotomy theorem, the most important concept in universal algebra is that of a polymorphism. An operation is a polymorphism of a relation if, for any choice of m tuples from R, it holds that the tuple obtained from these m tuples by applying f coordinate-wise, i.e., is in R. That is, an operation f is a polymorphism of R if R is closed under f: applying f to any tuples in R yields another tuple inside R. A set of relations Γ is said to have a polymorphism f if every relation in Γ has f has a polymorphism. This definition allows for the algebraic formulation of Schaefer's dichotomy theorem.

Let Γ be a finite constraint language over the Boolean domain. The problem CSP(Γ) is decidable in polynomial-time if Γ has one of the following six operations as a polymorphism:

1. the constant unary operation 0;
2. the constant unary operation 1;
3. the binary AND operation ∧;
4. the binary OR operation ∨;
5. the ternary majority operation
6. the ternary minority operation

Otherwise, the problem CSP(Γ) is NP-complete.

In this formulation, it is easy to check if any of the tractability conditions hold.