<p>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. </p>

<p>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}$. </p>

<p><strong>First</strong>: 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$. </p>

<p>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 <em>variables</em>,  not on <em>literals</em>.  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).</p>

<p><strong>Second</strong>: 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.</p>

<p>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.  </p>

<p>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.</p>

CC BY-SA 3.0
2012-01-23T13:46:26.283Z
To add to MassimoLauria's excellent answer; There is no contradiction. Have a look at this [Wikipedia](http://en.wikipedia.org/wiki/Constraint_satisfaction_problem) article which has a section that explains, in simple words, the relationship between Ladner's Theorem and Schaefer's Theorem.
Mohammad Al-Turkistany
CC BY-SA 3.0
2012-01-24T22:13:39.640Z
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
CC BY-SA 3.0
2012-01-25T10:46:44.387Z
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
CC BY-SA 3.0
2012-01-26T16:36:02.173Z
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
CC BY-SA 3.0
2012-01-27T04:07:02.777Z
@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
CC BY-SA 3.0
2012-01-23T12:06:29.963Z
2012-01-23T12:12:24.803Z
2012-01-23T12:12:24.803Z
MassimoLauria
<p>As Massimo Lauria states, problems of the form CSP($\Gamma$) are rather special.  So there is no contradiction.</p>

<p>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$.  </p>

<p>CSP($\Gamma$) is a special kind of constraint satisfaction problem.  It consists of <em>all</em> pairs of relational structures which are constructed using <em>only</em> 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.</p>

<p>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.</p>

CC BY-SA 3.0
2012-02-27T00:00:07.567Z
2013-01-09T14:13:01.230Z
2013-01-09T14:13:01.230Z
András Salamon
<p>While reading the article <a href="http://rjlipton.wordpress.com/2012/01/20/is-it-time-to-declare-victory-in-counting-complexity/#comments">"Is it Time to Declare Victory in Counting Complexity?"</a> over at the <a href="http://rjlipton.wordpress.com/">"Godel's Lost Letter and P=NP"</a> blog, they mentioned the dichotomy for CSP's.  After some link following, googling and wikipeding, I came across <a href="http://en.wikipedia.org/wiki/NP-intermediate">Ladner's Theorem</a>:</p>

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

<p>and to <a href="http://en.wikipedia.org/wiki/Schaefer%27s_dichotomy_theorem">Schaefer's theorem</a>:</p>

<blockquote>
  <p><b>Schaefer's Dichotomy Theorem:</b> 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.</p>
</blockquote>

<p>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.</p>

<p>What am I missing?  Why don't these two results contradict each other?</p>

<p>I took the condensed version of the above theorem statements from <a href="http://mtl.uta.fi/Opetus/seminaarit/AMTS/0304/CSP_miguel.ps">here</a>.  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".</p>

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

CC BY-SA 3.0
2012-01-23T13:45:32.917Z
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
CC BY-SA 3.0
2012-01-23T20:45:25.467Z
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
<cc.complexity-theory><np-hardness><complexity-classes><sat><csp>
Ladner's Theorem vs. Schaefer's Theorem
user834
# Ladner's Theorem vs. Schaefer's Theorem

(Asked by: username_0 on 2012-01-23)

While reading the article ["Is it Time to Declare Victory in Counting Complexity?"](http://rjlipton.wordpress.com/2012/01/20/is-it-time-to-declare-victory-in-counting-complexity/#comments) over at the ["Godel's Lost Letter and P=NP"](http://rjlipton.wordpress.com/) blog, they mentioned the dichotomy for CSP's. After some link following, googling and wikipeding, I came across [Ladner's Theorem](http://en.wikipedia.org/wiki/NP-intermediate):

> **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](http://en.wikipedia.org/wiki/Schaefer%27s_dichotomy_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](http://mtl.uta.fi/Opetus/seminaarit/AMTS/0304/CSP_miguel.ps). 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?

**Tags:** cc.complexity-theory, np-hardness, complexity-classes, sat, csp
> **Comments:**
> **username_1**: 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.  
> **username_2**: 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)$.  

---

## 2 answers

### Answer by username_6 on 2012-02-27. Score: 18 | Accepted answer

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 by username_3 on 2012-01-23. Score: 25

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.

> **Comments:**
> **username_4**: To add to MassimoLauria's excellent answer; There is no contradiction. Have a look at this [Wikipedia](http://en.wikipedia.org/wiki/Constraint_satisfaction_problem) article which has a section that explains, in simple words, the relationship between Ladner's Theorem and Schaefer's Theorem.  
> **username_0**: 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?  
> **username_3**: 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?  
> **username_5**: 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).  
> **username_0**: @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?  

---

