**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:

- the constant unary operation 0;
- the constant unary operation 1;
- the binary AND operation ∧;
- the binary OR operation ∨;
- the ternary majority operation
- 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.

Read more about this topic: Schaefer's Dichotomy Theorem

### Famous quotes containing the words presentation and/or modern:

“He uses his folly like a stalking-horse, and under the *presentation* of that he shoots his wit.”

—William Shakespeare (1564–1616)

“He was naturally so sensitive, and so kind. But he had the insidious *modern* disease of tolerance. He must tolerate everything, even a thing that revolted him.”

—D.H. (David Herbert)