File:Schaefer's dichotomy theorem relation hierarchy.gif

English: This Hasse diagram shows all ternary relations R on Boolean values that are invariant to argument permutation, i.e. such that R(x₁,x₂,x₃) holds iff R(x_σ(1),x_σ(2),x_σ(3)) holds, for every permutation σ of the set {1,2,3}; in order to determine if R holds on a triple it is sufficient to know the count of its true values.

An arrow from R₁ upwards to R₂ indicates that R₁(x₁,x₂,x₃) implies R₂(x₁,x₂,x₃). The set ot true-argument counts for which a relation holds is shown in the left of each node, while the right shows some mnemonic (nor: negated or, ae: all equal, maj: majority, min: minority, eqv: equivalence, nae: not all equal, n2in3: not exactly 2 arguments are true, n1in3: not exactly 1 argument is true, nand: negated and). The formal definition of all 16 relations is given by the table below.

According to Schaefer's dichotomy theorem, the problem of deciding the satisfiability of a generalized conjunctive normal form is either NP complete or in P, depending on the relation R employed to form generalized clauses. Correspondingly, the node of R is colored red and green, respectively.

Some particular cases that are discussed in more detail in English Wikipedia articles are linked via image annotations.

For the NP-complete relations, the reduction of or to each of them is shown below. For each combination of X, Y, Z, the relation or(X,Y,Z) holds iff appropriate values of the auxiliary variables a,...,d exist such that the reduction formula on the right-hand side holds. The reduction formulas are the shortest ones that were found by a brute-force search.