Ladner's Theorem vs. Schaefer's Theorem

Question

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?

Answer 1

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.

Answer 2

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.