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)?
$\begingroup$
$\endgroup$
9
-
22$\begingroup$ Why do people think this is such a bad question? $\endgroup$– Peter ShorCommented Jun 6, 2011 at 0:46
-
14$\begingroup$ 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. $\endgroup$– Shaun HarkerCommented Jun 6, 2011 at 1:16
-
12$\begingroup$ 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". $\endgroup$– JeffεCommented Jun 6, 2011 at 4:53
-
13$\begingroup$ Please read the paper "The complexity of satisfiability problems: Refining Schaefer's theorem". $\endgroup$– didestCommented Jun 6, 2011 at 16:49
-
3$\begingroup$ 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. $\endgroup$– KavehCommented Jun 7, 2011 at 0:14
|
Show 4 more comments
4 Answers
$\begingroup$
$\endgroup$
7
Here is a further intuitive and unpretentious explanation along the lines of MGwynne'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.
answered Jun 6, 2011 at 20:58
-
7$\begingroup$ I wish I could upvote this more! A much better answer! $\endgroup$– MGwynneCommented Jun 6, 2011 at 21:47
-
5$\begingroup$ @MGwynne: Thanks for your very kind comment. You're welcome, and your answer is indeed very good! $\endgroup$ Commented Jun 7, 2011 at 5:42
-
8$\begingroup$ 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! :) $\endgroup$ Commented Jun 22, 2011 at 10:58
-
4$\begingroup$ @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. $\endgroup$ Commented Jun 22, 2011 at 12:16
-
$\begingroup$ 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. $\endgroup$ Commented Aug 18, 2017 at 2:37
$\begingroup$
$\endgroup$
4
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.
-
3$\begingroup$ "You can't encode things like implication" -- IMP-SAT is also in P (and I think NL) $\endgroup$– MaxCommented Jun 7, 2011 at 13:41
-
8
-
1
-
1$\begingroup$ 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! $\endgroup$ Commented Aug 20, 2017 at 18:44
$\begingroup$
$\endgroup$
3
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:
(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.
(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.
(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.
answered Jun 6, 2011 at 23:10
-
2$\begingroup$ 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. $\endgroup$– KavehCommented Jun 7, 2011 at 0:26
-
3$\begingroup$ @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: cs.ox.ac.uk/publications/publication1610-abstract.html $\endgroup$ Commented Jun 7, 2011 at 0:33
-
3$\begingroup$ 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: cs.sfu.ca/~abulatov/papers/3-el-journal.ps Hybrid classes are also more interesting for larger domains. $\endgroup$ Commented Jun 7, 2011 at 18:41
$\begingroup$
$\endgroup$
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 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.
