3
$\begingroup$

Why is the reduction $\textbf{SAT} \leq_P \textbf{3SAT}$ possible, but $\textbf{SAT} \leq_P \textbf{2SAT}$ not possible, given, that $\textbf{SAT}$ is $\textbf{NP}$-complete, $\textbf{2SAT} \in \textbf{NP}$ and $\textbf{3SAT} \in \textbf{NP}$?

$\endgroup$
8
$\begingroup$

I believe the asker is wanting to know specifically why the standard approach to reducing $\text{SAT}$ to $\text{3SAT}$ does not continue to extend to the $\text{2SAT}$ case. Here is a walkthrough as to why.

Conversion of a SAT Instance to a 3-SAT Instance:

For convenience, let us assume everything is in $\text{CNF}$, or conjunctive normal form. The $\text{SAT} \le_p \text{3SAT}$ proof works by introducing dummy variables to spread the actual variables over multiple clauses.

Illustration: Consider a single clause in boolean formula $(x_1 \lor x_2 \lor x_3 \lor x_4)$. The $\text{3SAT}$ reduction works by introducing a dummy variable to represent a disjunction of two literals in hopes that it reduces the clause's length by one. For example, $y = x_3\lor x_4$. The clause can be rewritten as:

$(x_1 \lor x_2 \lor y) \land (\bar y \lor x_3 \lor x_4)$

Notice that these clauses are now in a $\text{CNF}$ for $\text{3SAT}$. If this is repeated multiple times for each clause, the final $\text{CNF}$ formula will be at most polynomial in length of the original. This is why a polynomial time reduction would suffice.

Attempting to Apply the Method to Convert to 2-SAT:

If we tried to use the trick above with a clause of length 3, $(a\lor b\lor c)$, then we would not get the desired improvement. Let our dummy variable here be $y=b \lor c$.

The result: $(a \lor y) \land (\bar y \lor b \lor c)$

As you can see, it still has a clause of size 3. If we used the method again on the second clause, we would end up with the same problem while also adding an additional clause of length 2.

It could be said that the simplest reason for this is because $\land$ and $\lor$ are binary operators. You still need to apply these operators on pairs of variables, then include an additional dummy variable (resulting in a clause of length 3).

There have been attempts at getting around this that are successful, but the resulting sequence of clauses become exponential in length. Handling such a formula is outside the scope of $\text{P}$, which is why such a reduction would not be a polynomial time reduction.

$\endgroup$
3
$\begingroup$

First of all, "not possible" is only under the assumption that $P\neq NP$.

While it is true that $2SAT\in NP$, we also know that $2SAT\in P$. Thus, if indeed $SAT\leq_p 2SAT$, then $P=NP$.

The reduction $SAT\le_p 3SAT$ is possible since we know that $3SAT$ is $NP$-complete, and therefore there is a reduction from every problem in $NP$ to $3SAT$.

$\endgroup$
  • $\begingroup$ Thanks for the quick response! But what is, if you only know, that $\textbf{SAT}$ is $\textbf{NP}$-complete, $\textbf{2SAT} \in \textbf{NP}$ and $\textbf{3SAT} \in \textbf{NP}$? Could you somehow argue starting with the reduction from $\textbf{SAT}$ to $\textbf{3SAT}$? $\endgroup$ – Anderson Sep 25 '13 at 16:10
  • 1
    $\begingroup$ @Anderson $2SAT \in NP$ doesn't particularly help you; there are classes of problems that are strict subsets of $NP$ (for example, take $SPACE(1)$), and the problems from those classes are obviously in $NP$ but can't possibly be $NP$-complete. $\endgroup$ – G. Bach Sep 25 '13 at 16:44
  • 1
    $\begingroup$ @Anderson You can't show that 2SAT isn't NP-complete just by showing that one particular proof technique doesn't work (e.g., the one used to prove that 3SAT is NP-complete). $\endgroup$ – David Richerby Sep 25 '13 at 21:18
  • $\begingroup$ If you don't know that $3SAT$ is $NP$-hard, then indeed - you cannot say that $SAT\le_p 3SAT$ (but that doesn't make it any less true). $\endgroup$ – Shaull Sep 26 '13 at 6:23
1
$\begingroup$

one way to conceptualize this: this can be seen as a case of a more general phenomenon where various problems are "simpler" for "small" fixed parameters of the problem. this happens with many NP complete problems but also outside of NP (eg with undecidable problems becoming decidable for small fixed parameters). see also 2SAT, wikipedia for the proof that 2SAT is in P.

another way/angle to understand this phenomenon is that the Tseitin transformation allows conversion of arbitrary circuits (including SAT itself) to 3SAT but some of the conversions require 3 variables (but none require more than 3).

yet another way to visualize this concept is with the SAT transition point where it is (theoretically/empirically) found that formulas of particular structure move from "hard-easy-hard" based on alteration of basic form, in particular (with SAT) the clause/variable ratio, but the transition point phenomenon is known to apply to all NP complete problems.[1] in this case the (average) number of variables in clauses is also a source of a transition point from hard to easy.

[1] Phase transition behavior Toby Walsh

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.