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?
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.