Dichotomy

Way back at the dawn of complexity theory, it was proven that the problem of deciding whether an arbitrary 3-CNF formula is satisfiable is NP-Complete. Here, 3-CNF means that in conjunctive normal form, each clause has three literals. Say that your 3-CNF formula is built from k variables. One way to model the satisfiability problem is to attach to each clause the set of all k-tuples that satisfy that clause. The satisfiability problem then boils down to deciding whether these sets have a nontrivial intersection.

We can abstract things a little here. The tuples we considered above are, of course, k-ary relations on the alphabet {0,1}. Start by taking a collection of relations on {0,1} of arbitrary, but finite, rank. Now, build a formula by using existential quantification of variables as well as conjunctions of relations on those symbols. In other words, conjunction of things that say stuff like "(x1,x2,x3) is in relation R". What we have now is something called a boolean constraint satisfaction problem. We may very well be interested in the complexity of such problems.

Let X be a set of these sorts of relations. Then, the "Schaefer Dichotomy Theorem" says that deciding whether the constraint problem for X is satisfiable is in P if and only if one of the folloing conditions holds:
(1) Every relation in X contains a tuple in which all entries are 0
(2) Every relation in X contains a tuple in which all entries are 1
(3) Every relation in X is definable by a conjunction of horn clauses
(4) Every relation in X is definable by a formula by a formula in CNF in which each clause contains at most one unnegated variable.
(5) Every relation in X is definable by a 2-CNF formula
(6) Every relation in X is the set of solutions of a set of linear equations over {0,1}, considered as a field.
Otherwise, the problem is NP-Complete.

This result is contained in:

The complexity of satisfiability problems, Thomas J. Schaefer

We might be interested in extending this "dichotomy" to arbitrary constraint satisfaction problems (CSPs). This is considered in the following paper, where it is also shown that there is a strong connection to the algebraic notion of "clones":

Classifying the Complexity of Constraints using Finite Algebras; Bulatov, Jeavons and Krokhin.

They state Schaeffer's dichotomy theorem in the special case of boolean CSPs where each operation is actually a function. It turns out that a set of such operations is tractable (i.e., the corresponding problem is in P) if it contains an essentially non-unary operation. Otherwise it is NP-Complete. What is an essentially non-unary operation? Well, it is an n-ary function whose value does not depend on only one coordinate as, say, the projection functions do.

This is all quite neat. However, times have changed and P is no longer considered all that tractable. Can we get a more refined analysis of the cases in the Dichotomy Theorem? The answer is yes, and is considered in the following paper, which also uses clones:

The Complexity of Satisfiability Problems: Refining Schaefer's Theorem

For those who prefer categorical language, a clone is what is also known as an "algebraic theory". That is, take a category, C, which has finite products. An algebraic theory is more or less the image of a functor from C to the category of sets that preserves finite products.