Шеффердің дихотомия теоремасы: Қатынастар жиынының күрделігі

When a finite set S of relations yields polynomial time or NP complete problems
In computational complexity theory, a branch of computer science, Schaefer's dichotomy theorem, proved by Thomas Jerome Schaefer, states necessary and sufficient conditions under which a finite set S of relations over the Boolean domain yields polynomial time or NP complete problems when the relations of S are used to constrain some of the propositional variables. It is called a dichotomy theorem because the complexity of the problem defined by S is either in P or is NP complete, as opposed to one of the classes of intermediate complexity that is known to exist (assuming P ≠ NP) by Ladner's theorem. Special cases of Schaefer's dichotomy theorem include the NP completeness of SAT (the Boolean satisfiability problem) and its two popular variants 1 in 3 SAT and not all equal 3SAT (often denoted by NAE 3SAT). In fact, for these two variants of SAT, Schaefer's dichotomy theorem shows that their monotone versions (where negations of variables are not allowed) are also NP complete.

The analysis was later fine tuned: CSP(Γ) is either solvable in co NLOGTIME, L complete, NL complete, ⊕L complete, P complete or NP complete, and given Γ, one can decide in polynomial time which of these cases holds. Schaefer's dichotomy theorem has also been generalized to use propositional logic of graphs instead of Boolean logic.

If the problem is to count the number of solutions, which is denoted by #CSP(Γ), then there is a similar result for the binary domain by Creignou and Hermann. Specifically, a finite set of relations S over the Boolean domain defines a polynomial time computable satisfiability problem if every relation in S is equivalent to a conjunction of affine formulae. Let Γ be a finite constraint language over the Boolean domain. If the problem #CSP(Γ) is computable in polynomial time, then Γ has a Mal'tsev operation as a polymorphism. Otherwise, the problem #CSP(Γ) is #P complete. A Mal'tsev operation m is a ternary operation that satisfies An example of a Mal'tsev operation is the Minority operation given in the modern, algebraic formulation of Schaefer's dichotomy theorem above. Thus, when Γ has the Minority operation as a polymorphism, it is not only possible to decide CSP(Γ) in polynomial time, but to compute #CSP(Γ) in polynomial time. There are a total of 4 Mal'tsev operations on Boolean variables, determined by the values of and An example of a less symmetric one is given by On other domains, such as groups, examples of Mal'tsev operations include and
For larger domains, even for a domain of size three, the existence of a Mal'tsev polymorphism for Γ is an insufficient condition for the tractability of #CSP(Γ). However, the absence of a Mal'tsev polymorphism for Γ implies the #P hardness of #CSP(Γ).