<p>Consider resolution on a 2-SAT formula. Any resolvent is of size at most 2 (note that $n + m -2 \le 2$ if $n, m \le 2$ for clauses of length $n$ and $m$ resp). The number of clauses of size 2 is quadratic in the number of variables. Therefore, the resolution algorithm is in P.</p>

<p>Once you get to 3-SAT you can get bigger and bigger resolvents, so it all goes pear-shaped :).</p>

<p>Try translating a problem into 2-SAT. As you can't have clauses of size 3, you can't (in general) encode implications involving 3 variables or more, for instance that one variable is the result of a binary operation on two others. This is a huge restriction.</p>

CC BY-SA 3.0
2011-06-07T13:41:48.737Z
"You can't encode things like implication" -- IMP-SAT is also in P (and I think NL)
Max
CC BY-SA 3.0
2011-06-08T03:47:27.310Z
$p \to q$ is just $\lnot p \lor q$.
Kaveh
CC BY-SA 3.0
2011-06-08T05:43:02.947Z
Kaveh, good point, fixed now.
MGwynne
CC BY-SA 3.0
2017-08-20T18:44:07.167Z
As I said already when you have reduced your arbitrary NP problem to either Boolean Satisfiability or Circuit SAT or CNF SAT, do **not** reduce the problem to 3SAT, because the problem becomes even more harder and complex with more boolean variables and clauses. Even resolution algorithm becomes lesser efficient in the new problem!
Farewell Stack Exchange
CC BY-SA 3.0
2011-06-05T20:05:11.460Z
2011-06-08T05:52:23.883Z
2011-06-08T05:52:23.883Z
MGwynne
<p>As Walter says, clauses of 2-SAT have a special form.  This can be exploited to find solutions quickly.</p>

<p>There are actually several classes of SAT instances that can be decided in polynomial time, and 2-SAT is just one of these <em>tractable classes</em>.  There are three broad kinds of reasons for tractability:</p>

<ol>
<li><p>(Structural tractability) Any class of SAT instances where the variables interact in a tree-like fashion can be solved in polynomial time.  The degree of the polynomial depends on the maximum <em>width</em> of instances in the class, where the width measures how far an instance is from being a tree.  More precisely, Marx showed that if the instances have bounded submodular width, then the class can be decided in polynomial time using a divide-and-conquer approach.</p></li>
<li><p>(Language tractability) Any class of SAT instances where the pattern of true-false variables is "nice", can be solved in polynomial time.  More precisely, the pattern of literals defines a language of relations, and Schaefer classified the six languages that lead to tractability, each with its own algorithm.  2-SAT forms one of the six Schaefer classes.</p></li>
<li><p>(Hybrid tractability) There are also some classes of instances that do not fall into the other two categories, but which can be solved in polynomial time for other reasons.</p>

<ul>
<li>Dániel Marx, <em>Tractable hypergraph properties for constraint satisfaction and conjunctive queries</em>, STOC 2010. (<a href="http://dx.doi.org/10.1145/1806689.1806790">doi</a>, <a href="http://arxiv.org/abs/0911.0801">preprint</a>)</li>
<li>Thomas J. Schaefer, <em>The complexity of satisfiability problems</em>, STOC 1978. (<a href="http://dx.doi.org/10.1145/800133.804350">doi</a>)</li>
</ul></li>
</ol>

CC BY-SA 3.0
2011-06-07T00:26:48.623Z
There are also arguments based on the structure of the solution space from the random k-SAT literature that can be used to explain the difference.
Kaveh
CC BY-SA 3.0
2011-06-07T00:33:27.513Z
@Kaveh: my description of hybrid tractability was supposed to be vague enough to encompass such things.  For instance, for very special kinds of instances one can make an argument for satisfiability based on the Lovász Local Lemma.  See the 1997 survey by Pearson and Jeavons: http://www.cs.ox.ac.uk/publications/publication1610-abstract.html
András Salamon
CC BY-SA 3.0
2011-06-07T18:41:59.750Z
Also note that SAT is the special case of the constraint satisfaction problem where every variable can take 2 values.  When variables can take 3 values, there are 10 tractable language classes, classified by Andrei Bulatov: http://www.cs.sfu.ca/~abulatov/papers/3-el-journal.ps  Hybrid classes are also more interesting for larger domains.
András Salamon
CC BY-SA 3.0
2011-06-06T23:10:25.673Z
2011-06-06T23:10:25.673Z
András Salamon
<p>If you understand the algorithm for 2SAT, you already know why it's in P - this is precisely what the algorithm demonstrates. I think <a href="http://www.smbc-comics.com/index.php?db=comics&amp;id=1914#comic">this comic</a> illustrates my point. As you already know why 2SAT is in P, what you probably want to know is why 2SAT isn't NP-hard.</p>

<p>To understand why 2SAT isn't NP-hard, you have to consider how easy it is to reduce other problems in NP to it. To get an intuitive understanding of this, look at how SAT can be reduced to 3SAT and try to apply the same techniques to reduce SAT to 2SAT. 2SAT is just not as expressive as 3SAT and other SAT variants.</p>

CC BY-SA 3.0
2011-06-09T08:06:48.293Z
2011-06-09T08:06:48.293Z
Dave
<p>Here is a further intuitive and unpretentious explanation along the lines of MGwynne's answer.</p>

<p>With $2$-SAT, you can only express implications of the form $a \Rightarrow b$, where $a$ and $b$ are literals. More precisely, every $2$-clause $l_1 \lor l_2$ can be understood as a pair of implications: $\lnot l_1 \Rightarrow l_2$ and $\lnot l_2 \Rightarrow l_1$. If you set $a$ to true, $b$ must be true as well. If you set $b$ to false, $a$ must be false as well. Such implications are straightforward: there is no choice, you have only $1$ possibility, there is no room for case-multiplication. You can just follow every possible implication chain, and see if you ever derive both $\lnot l$ from $l$ and $l$ from $\lnot l$: if you do for some $l$, then the 2-SAT formula is unsatisfiable, otherwise it is satisfiable. It is the case that the number of possible implication chains is polynomially bounded in the size of the input formula.</p>

<p>With $3$-SAT, you can express implications of the form $a \Rightarrow b \lor c$, where $a$, $b$ and $c$ are literals. Now you are in trouble: if you set $a$ to true, then either $b$ or $c$ must be true, but which one? You have to make a choice: you have 2 possibilities. Here is where case-multiplication becomes possible, and where the combinatorial explosion arises.</p>

<p>In other words, $3$-SAT is able to express the presence of more than one possibility, while $2$-SAT doesn't have such ability. It is precisely such presence of more than one possibility ($2$ possibilities in case of $3$-SAT, $k-1$ possibilities in case of $k$-SAT) that causes the typical combinatorial explosion of NP-complete problems. </p>

CC BY-SA 3.0
2011-06-06T21:47:42.420Z
I wish I could upvote this more! A much better answer!
MGwynne
CC BY-SA 3.0
2011-06-07T05:42:24.987Z
@MGwynne: Thanks for your very kind comment. You're welcome, and your answer is indeed very good!
Giorgio Camerani
CC BY-SA 3.0
2011-06-22T10:58:13.323Z
This is a nice answer to a good question (IMHO). As Mac Lane has written: "Effective or tricky formal manipulations are introduced by Mathematicians who doubtless have a guiding idea---but it is easier to state the manipulations than to formulate the idea in words. ... A perspicacious exposition of a piece of Mathematics lets the ideas shine through the display of manipulations."  This particular question-and-answer helped 
"the ideas shine through" (for me).  Thanks! :)
John Sidles
CC BY-SA 3.0
2011-06-22T12:16:37.017Z
@John: You're very welcome! ;-) Many thanks for your great and generous comment, I've really appreciated it. I couldn't agree more with Mac Lane words.
Giorgio Camerani
CC BY-SA 3.0
2017-08-18T02:37:42.720Z
According to Giorgio Camerani's answer this is **not** worthwhile to reduce any NP problem to 3SAT if you introduce more dummy boolean variables, have more clauses and have **neither** gain **nor** profit, but it is more preferred to reduce it to either CNF SAT or boolean satisfiability or Circuit SAT instead, because in these problems you have lesser boolean variables and lesser clauses and that means that brute force naive algorithms, karnaugh maps and Quine-McClusky algorithm have better complexity :D.
Farewell Stack Exchange
CC BY-SA 4.0
2020-07-04T20:31:16.183Z
I find it paradoxical that a trivial size difference between the two.
The T
CC BY-SA 4.0
2022-01-18T08:03:47.607Z
I would like to see a proof (at least a sketch) for `if you ever derive both ¬l from l and l from ¬l: if you do for some l, then the 2-SAT formula is unsatisfiable, otherwise it is satisfiable.`
mathematics-and-caffeine
CC BY-SA 3.0
2011-06-06T20:58:07.457Z
2011-06-07T05:44:12.847Z
2011-06-07T05:44:12.847Z
Giorgio Camerani
<p>I've come across the polynomial algorithm that solves 2SAT. I've found it boggling that 2SAT is in P where all (or many others) of the SAT instances are NP-Complete. What makes this problem different? What makes it <em>so</em> easy (NL-Complete - even easier than P)? </p>

CC BY-SA 3.0
2011-06-06T00:46:43.730Z
Why do people think this is such a bad question?
Peter Shor 
CC BY-SA 3.0
2011-06-06T01:13:34.207Z
@Peter, right now the question has 3 close votes (but strangely no comments). I am guessing that they feel this is an elementary question since the OP is not familiar with the topic and therefore it doesn't look like that the OP is asking for a deep explanation of the difference.
Kaveh
CC BY-SA 3.0
2011-06-06T01:16:04.940Z
One interesting aspect is that if you want to know the maximum number of simultaneously satisfiable clauses in a 2SAT expression (i.e. Max2SAT) then you are back to NP-complete again.
Shaun Harker
CC BY-SA 3.0
2011-06-06T03:20:51.760Z
Related answer: http://cstheory.stackexchange.com/questions/5584/what-are-the-root-difficulties-in-going-from-graphs-to-hypergraphs/5588#5588
Hsien-Chih Chang 張顯之
CC BY-SA 3.0
2011-06-06T04:53:26.207Z
This is either a horrible question, because it doesn't have a useful answer, or a fantastic question, because the only correct answer is "nobody knows".
Jeffε
CC BY-SA 3.0
2011-06-06T13:42:06.183Z
I wasn't aiming for an elementary question. Although I don't consider myself as an expert in complexity theory (that's why I'm asking the question in the first place..) I do think I have the basic understanding in this topic. I was hoping for a (deep) explanation why is 3SAT so much more harder than 2SAT. From a high level glance, it doesn't seem these two problems are *so* far apart. Intuitively, I would have expected that if one is NP-complete the other would be solvable in a high degree polynomial time (O(n^100) for example but not O(n^2) and below).
Guy
CC BY-SA 3.0
2011-06-06T16:49:22.790Z
Please read the paper "The complexity of satisfiability problems: Refining Schaefer's theorem".
didest
CC BY-SA 3.0
2011-06-06T23:18:08.523Z
@JɛﬀE: I'm not so sure that the question has no useful answer, nor that "nobody knows".
András Salamon
CC BY-SA 3.0
2011-06-07T00:14:26.813Z
Dear Guy, the fact that 2SAT is in P is covered in almost every standard complexity textbook, so when you say that you just noticed this fact makes the question look like as if you have not even read a standard textbook in complexity.
Kaveh
<cc.complexity-theory><np-hardness><big-picture><polynomial-time>
Why is 2SAT in P?
Guy
# Why is 2SAT in P?

(Asked by: username_0 on 2011-06-05)

I've come across the polynomial algorithm that solves 2SAT. I've found it boggling that 2SAT is in P where all (or many others) of the SAT instances are NP-Complete. What makes this problem different? What makes it *so* easy (NL-Complete - even easier than P)?

**Tags:** cc.complexity-theory, np-hardness, big-picture, polynomial-time

> **Comments:**
> **username_1**: Why do people think this is such a bad question?  
> **username_2**: @Peter, right now the question has 3 close votes (but strangely no comments). I am guessing that they feel this is an elementary question since the OP is not familiar with the topic and therefore it doesn't look like that the OP is asking for a deep explanation of the difference.  
> **username_3**: One interesting aspect is that if you want to know the maximum number of simultaneously satisfiable clauses in a 2SAT expression (i.e. username_92SAT) then you are back to NP-complete again.  
> **username_4**: Related answer: http://cstheory.stackexchange.com/questions/5584/what-are-the-root-difficulties-in-going-from-graphs-to-hypergraphs/5588#5588  
> **username_5**: This is either a horrible question, because it doesn't have a useful answer, or a fantastic question, because the only correct answer is "nobody knows".  
> **username_0**: I wasn't aiming for an elementary question. Although I don't consider myself as an expert in complexity theory (that's why I'm asking the question in the first place..) I do think I have the basic understanding in this topic. I was hoping for a (deep) explanation why is 3SAT so much more harder than 2SAT. From a high level glance, it doesn't seem these two problems are *so* far apart. Intuitively, I would have expected that if one is NP-complete the other would be solvable in a high degree polynomial time (O(n^100) for example but not O(n^2) and below).  
> **username_6**: Please read the paper "The complexity of satisfiability problems: Refining Schaefer's theorem".  
> **username_7**: @JɛﬀE: I'm not so sure that the question has no useful answer, nor that "nobody knows".  
> **username_2**: Dear username_0, the fact that 2SAT is in P is covered in almost every standard complexity textbook, so when you say that you just noticed this fact makes the question look like as if you have not even read a standard textbook in complexity.  

---

## 4 answers

### Answer by username_12 on 2011-06-06. Score: 109 | Accepted answer

Here is a further intuitive and unpretentious explanation along the lines of username_8's answer.

With $2$-SAT, you can only express implications of the form $a \Rightarrow b$, where $a$ and $b$ are literals. More precisely, every $2$-clause $l\_1 \lor l\_2$ can be understood as a pair of implications: $\lnot l\_1 \Rightarrow l\_2$ and $\lnot l\_2 \Rightarrow l\_1$. If you set $a$ to true, $b$ must be true as well. If you set $b$ to false, $a$ must be false as well. Such implications are straightforward: there is no choice, you have only $1$ possibility, there is no room for case-multiplication. You can just follow every possible implication chain, and see if you ever derive both $\lnot l$ from $l$ and $l$ from $\lnot l$: if you do for some $l$, then the 2-SAT formula is unsatisfiable, otherwise it is satisfiable. It is the case that the number of possible implication chains is polynomially bounded in the size of the input formula.

With $3$-SAT, you can express implications of the form $a \Rightarrow b \lor c$, where $a$, $b$ and $c$ are literals. Now you are in trouble: if you set $a$ to true, then either $b$ or $c$ must be true, but which one? You have to make a choice: you have 2 possibilities. Here is where case-multiplication becomes possible, and where the combinatorial explosion arises.

In other words, $3$-SAT is able to express the presence of more than one possibility, while $2$-SAT doesn't have such ability. It is precisely such presence of more than one possibility ($2$ possibilities in case of $3$-SAT, $k-1$ possibilities in case of $k$-SAT) that causes the typical combinatorial explosion of NP-complete problems.

> **Comments:**
> **username_8**: I wish I could upvote this more! A much better answer!  
> **username_12**: @username_8: Thanks for your very kind comment. You're welcome, and your answer is indeed very good!  
> **username_13**: This is a nice answer to a good question (IMHO). As Mac Lane has written: "Effective or tricky formal manipulations are introduced by Mathematicians who doubtless have a guiding idea---but it is easier to state the manipulations than to formulate the idea in words. ... A perspicacious exposition of a piece of Mathematics lets the ideas shine through the display of manipulations."  This particular question-and-answer helped  "the ideas shine through" (for me).  Thanks! :)  
> **username_12**: @John: You're very welcome! ;-) Many thanks for your great and generous comment, I've really appreciated it. I couldn't agree more with Mac Lane words.  
> **username_10**: According to username_12's answer this is **not** worthwhile to reduce any NP problem to 3SAT if you introduce more dummy boolean variables, have more clauses and have **neither** gain **nor** profit, but it is more preferred to reduce it to either CNF SAT or boolean satisfiability or Circuit SAT instead, because in these problems you have lesser boolean variables and lesser clauses and that means that brute force naive algorithms, karnaugh maps and Quine-McClusky algorithm have better complexity :D.  
> **username_14**: I find it paradoxical that a trivial size difference between the two.  
> **username_15**: I would like to see a proof (at least a sketch) for `if you ever derive both ¬l from l and l from ¬l: if you do for some l, then the 2-SAT formula is unsatisfiable, otherwise it is satisfiable.`  

---

### Answer by username_8 on 2011-06-05. Score: 31

Consider resolution on a 2-SAT formula. Any resolvent is of size at most 2 (note that $n + m -2 \le 2$ if $n, m \le 2$ for clauses of length $n$ and $m$ resp). The number of clauses of size 2 is quadratic in the number of variables. Therefore, the resolution algorithm is in P.

Once you get to 3-SAT you can get bigger and bigger resolvents, so it all goes pear-shaped :).

Try translating a problem into 2-SAT. As you can't have clauses of size 3, you can't (in general) encode implications involving 3 variables or more, for instance that one variable is the result of a binary operation on two others. This is a huge restriction.

> **Comments:**
> **username_9**: "You can't encode things like implication" -- IMP-SAT is also in P (and I think NL)  
> **username_2**: $p \to q$ is just $\lnot p \lor q$.  
> **username_8**: username_2, good point, fixed now.  
> **username_10**: As I said already when you have reduced your arbitrary NP problem to either Boolean Satisfiability or Circuit SAT or CNF SAT, do **not** reduce the problem to 3SAT, because the problem becomes even more harder and complex with more boolean variables and clauses. Even resolution algorithm becomes lesser efficient in the new problem!  

---

### Answer by username_7 on 2011-06-06. Score: 20

As Walter says, clauses of 2-SAT have a special form. This can be exploited to find solutions quickly.

There are actually several classes of SAT instances that can be decided in polynomial time, and 2-SAT is just one of these *tractable classes*. There are three broad kinds of reasons for tractability:

1. (Structural tractability) Any class of SAT instances where the variables interact in a tree-like fashion can be solved in polynomial time. The degree of the polynomial depends on the maximum *width* of instances in the class, where the width measures how far an instance is from being a tree. More precisely, Marx showed that if the instances have bounded submodular width, then the class can be decided in polynomial time using a divide-and-conquer approach.
2. (Language tractability) Any class of SAT instances where the pattern of true-false variables is "nice", can be solved in polynomial time. More precisely, the pattern of literals defines a language of relations, and Schaefer classified the six languages that lead to tractability, each with its own algorithm. 2-SAT forms one of the six Schaefer classes.
3. (Hybrid tractability) There are also some classes of instances that do not fall into the other two categories, but which can be solved in polynomial time for other reasons.

   * Dániel Marx, *Tractable hypergraph properties for constraint satisfaction and conjunctive queries*, STOC 2010. ([doi](http://dx.doi.org/10.1145/1806689.1806790), [preprint](http://arxiv.org/abs/0911.0801))
   * Thomas J. Schaefer, *The complexity of satisfiability problems*, STOC 1978. ([doi](http://dx.doi.org/10.1145/800133.804350))

> **Comments:**
> **username_2**: There are also arguments based on the structure of the solution space from the random k-SAT literature that can be used to explain the difference.  
> **username_7**: @username_2: my description of hybrid tractability was supposed to be vague enough to encompass such things.  For instance, for very special kinds of instances one can make an argument for satisfiability based on the Lovász Local Lemma.  See the 1997 survey by Pearson and Jeavons: http://www.cs.ox.ac.uk/publications/publication1610-abstract.html  
> **username_7**: Also note that SAT is the special case of the constraint satisfaction problem where every variable can take 2 values.  When variables can take 3 values, there are 10 tractable language classes, classified by Andrei Bulatov: http://www.cs.sfu.ca/~abulatov/papers/3-el-journal.ps  Hybrid classes are also more interesting for larger domains.  

---

### Answer by username_11 on 2011-06-09. Score: 11

If you understand the algorithm for 2SAT, you already know why it's in P - this is precisely what the algorithm demonstrates. I think [this comic](http://www.smbc-comics.com/index.php?db=comics&id=1914#comic) illustrates my point. As you already know why 2SAT is in P, what you probably want to know is why 2SAT isn't NP-hard.

To understand why 2SAT isn't NP-hard, you have to consider how easy it is to reduce other problems in NP to it. To get an intuitive understanding of this, look at how SAT can be reduced to 3SAT and try to apply the same techniques to reduce SAT to 2SAT. 2SAT is just not as expressive as 3SAT and other SAT variants.


---

