SAT not reducible to 2SAT

Question

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}$?

Answer 1

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.

Answer 2

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

Answer 3

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