That Logic Blog

May 24, 2005


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.


Anonymous Anonymous said...

Jon, this is indeed a nice result. Incidentally, this posting reminded me of a *similar* dichotomy result for existential second-order logic model-checking problem over graphs.

Fact: ESO logic model-checking problem over graphs is NP-complete. [We actually have a stronger result: a property of graph is in NP iff it is definable by an ESO-formula.]

For this dichotomy result, see Gottlob, Kolaitis, and Schwentick "Existential Second-Order Logic Over Graphs: Charting the Tractability Frontier", JACM, March 2004. You may like this paper too. 

Posted by Anthony Widjaja To

5:20 PM  
Anonymous Anonymous said...

Hi Anthony, thanks for the reference.

The ESO result isn't *quite* a dichotomy in the same sense as Schaefer's result. That is, the collection of graph properties *not* expressible in ESO fall in lots of different complexity classes. However, Schaefer's dichotomy is that the problem is either NP-Complete or in P.  

Posted by Jon

9:49 PM  
Anonymous Anonymous said...

Reminds me of all the results that say that various things are either countable or at least the size of the continuum. It seems that there might be somewhat of an analogy there, but I guess in the P/NP-complete case it's not even clear that the two possibilities are distinct, much less that there's anything in between! 

Posted by Kenny Easwaran

4:54 AM  

Post a Comment

<< Home