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.

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)