# Ladner's Theorem vs. Schaefer's Theorem

While reading the article "Is it Time to Declare Victory in Counting Complexity?" over at the "Godel's Lost Letter and P=NP" blog, they mentioned the dichotomy for CSP's. After some link following, googling and wikipeding, I came across Ladner's Theorem:

Ladner's Theorem: If ${\bf P} \ne {\bf NP}$, then there are problems in ${\bf NP} \setminus {\bf P}$ that are not ${\bf NP}$-complete.

and to Schaefer's theorem:

Schaefer's Dichotomy Theorem: For every constraint language $\ \Gamma$ over $\{0, 1\}$, if $\ \Gamma$ is Schaefer then ${\bf CSP}(\Gamma)$ is polynomial time solvable. Otherwise, ${\bf CSP}(\Gamma)$ is ${\bf NP}$-complete.

I read this to mean that, by Ladner's, there are problems that are neither ${\bf P}$ nor ${\bf NP}$-complete, but by Schaefer's, problems are either ${\bf P}$ and ${\bf NP}$-complete only.

What am I missing? Why don't these two results contradict each other?

I took the condensed version of the above theorem statements from here. In his "Final Comments" section, he says "Thus, if a problem is in ${\bf NP} \setminus {\bf P}$ but it is not ${\bf NP}$-complete then it can not be formulated as CSP".

Does this mean ${\bf SAT}$ problems miss some instances that are in ${\bf NP}$? How is that possible?

• Isn't there a slight issue in that one needs to be careful how one defines "constraint language" and "problem"? Schaefers theorem (as far as I recall), only considers languages given by taking the closure under conjunction and variable substitution of some set S of relations. However, one can construct sets of constraints problems which are not covered by this, and so can be tractable but not Schaefer. Presumably the set of problems Ladner constructs just isn't definable in terms of the closure under conjunction and variable substitution of a set of relations. – MGwynne Jan 23 '12 at 13:45
• I think you should change the last sentence since an instance does not have (non-trivial) complexity, sets of instances have complexity. Then it would mean that no NPI set of $\mathsf{SAT}$ instances is expressible as $\mathsf{CSP}(\Gamma)$. – Kaveh Jan 23 '12 at 20:45

As Massimo Lauria states, problems of the form CSP($\Gamma$) are rather special. So there is no contradiction.

Any constraint satisfaction problem instance can be represented as a pair $(S,T)$ of relational structures $S$ and $T$, and one has to decide if there exists a relational structure homomorphism from the source $S$ to the target $T$.

CSP($\Gamma$) is a special kind of constraint satisfaction problem. It consists of all pairs of relational structures which are constructed using only the relations from $\Gamma$ in the target relational structure: CSP($\Gamma$) = $\{(S,T) \mid \text{all relations of } T \text{ are from } \Gamma\}$. Schaefer's Theorem says that when $\Gamma$ contains only relations over $\{0,1\}$, then CSP($\Gamma$) is either NP-complete or in P, but says nothing at all about other collections of CSP instances.

As an extreme example, one can start with some CSP($\Gamma$) that is NP-complete, and "blow holes" in the language. (Ladner did this with SAT in the proof of his theorem.) The result is a subset containing only some of the instances, and no longer in the form CSP($\Gamma'$) for any $\Gamma'$. Repeating the construction yields an infinite hierarchy of languages of decreasing hardness, assuming P ≠ NP.

You need to understand that $\mathsf{CSP}$ problems have a structure that generic $\mathbf{SAT}$ problems do not have. I will give you a simple example. Let $\Gamma=\{\{(0,0),(1,1)\},\{(0,1),(1,0)\}\}$. This language is such that you can only express equality and inequality between two variables. Clearly any such set of constraints is solvable in polynomial time.

I will give you two arguments to clarify the relation between $\mathsf{CSP}$ and clauses. Notice that all that follows assumes $\mathbf{P}\not=\mathbf{NP}$.

First: constraints have a fixed number of variables, while the encoding of intermediate problems may need large clauses. This is not necessarily an issue when such large constraints can be expressed as a conjunction of small ones using auxiliary variables. Unfortunately this is not always the case for general $\Gamma$.

Assume $\Gamma$ to just contain the $\mathsf{OR}$ of five variables. Clearly you can express the $\mathsf{OR}$ of less variables by repeating inputs. You cannot express a larger $\mathsf{OR}$ because the way to do it using extension variables requires disjunctions of positive and negative literals. $\Gamma$ represents relations on variables, not on literals. Indeed when you think about 3-$\mathbf{SAT}$ as a $\mathsf{CSP}$ you need $\Gamma$ to contain four relations of disjunction with some negated inputs (from zero to three).

Second: each relation in $\Gamma$ can be expressed as a batch of clauses with (say) three literals. Each constraint must be a whole batch of such clauses. In the example with equality/inequality constraints you cannot have a binary $\mathsf{AND}$ (i.e. relation ${(1,1)}$) without enforcing a binary negated $\mathsf{OR}$ (i.e. relation ${(0,0)}$) on the same variables.

I hope this illustrates to you that $\mathbf{SAT}$ instances obtained from $\mathsf{CSP}$s have a very peculiar structure, which is enforced by the nature of $\Gamma$. If the structure is too tight then you cannot express hard problems.

A corollary of Schaefer Theorem is that whenever $\Gamma$ enforces a structure loose enough to express $\mathbf{NP\backslash P}$ decision problems, then the same $\Gamma$ allows enough freedom to express general 3-$\mathsf{SAT}$ instances.

• To add to MassimoLauria's excellent answer; There is no contradiction. Have a look at this Wikipedia article which has a section that explains, in simple words, the relationship between Ladner's Theorem and Schaefer's Theorem. – Mohammad Al-Turkistany Jan 23 '12 at 13:46
• Just to be sure I understand, you're saying that the restricted version of ${\bf CSP}$'S in Schaefer's theorem either are not able to encode an arbitrary 3-${\bf SAT}$ instance or that instances of ${\bf CSP}(\Gamma)$ could grow super-polynomially for some class of 3-${\bf SAT}$ problems? – user834 Jan 24 '12 at 22:13
• In Schaefer's Theorem several types of $\Gamma$ are shown to induce polynomial time algorithms. I think (but I'm not sure) that some of them cannot express a generic 3-$\mathbf{SAT}$ at all. Nevertheless consider $\Gamma$ to be the set of "Horn 3-clauses". These are polytime decidable and any deterministic computation in time $t$ can be encoded as a $\mathsf{Horn}$-$\mathbf{SAT}$ formula of size $poly(t)$. Thus I guess you can encode an exponentially long computations with an exponentially long $\mathsf{CSP}$ (i.e. exponentially many variables). Does it make sense? – MassimoLauria Jan 25 '12 at 10:46
• I think the right way to say it is that CSP's in Schaefer's framework cannot encode an arbitrary NP problem (3-SAT is in fact a canonical CSP problem). Note that this is a conditional statement (unless P=NP). – Chandra Chekuri Jan 26 '12 at 16:36
• @ChandraChekuri, Please excuse me for being so dense, but are you saying that CSP's in Schaefer's framework cannot encode arbitrary instances of 3-SAT? CSP can, in general, encode 3-SAT but the restricted version of CSP's in Schaefer's framework cannot? – user834 Jan 27 '12 at 4:07