Expressing 3SAT clause as a 2SAT formula

Question

I am wondering about expressing $3SAT$ clause (disjunction of 3 literals) as a $2SAT$ formula. If it would be possible then $P=NP$

Let's consider a clause of the form: $x_1 \vee x_2 \vee x_3$ The question is: is there a $2SAT-CNF$ encoding of the constraint that at least one of the $x1, x2, x3$ is $true$ ? (possibly such encoding can use a lot of additional variables and clauses...) I am curious if anybody has proven that such encoding simply does not exist.

More background: I recently went through following paper: SAT Encodings of the At-Most-k Constraint Just wondering what can be encoded purely within $2SAT$

Answer 1

Suppose you have a representation of $x_1\lor x_2\lor x_3$ as 2CNF clauses, possibly involving with hidden variables. (This would "represent" the three-way disjunction in the sense that the 2CNF is satisfiable together with any consistent combination of $(\neg)x_i$ that contains at least one positive $x_i$, and is not satisfiable together with $\neg x_1 \land \neg x_2 \land \neg x_3$.

First any hidden variable $h$ can be eliminated by replacing all clauses involving $h$ or $\neg h$, by the result of applying resolution to every combination of such clauses that has $h$ in one and $\neg h$ in another. This does not change the satisfiability of the formula. (Here an important observation is that using resolution on two 2-clauses produces another 2-clause; the is not true for clauses of higher arity).

Thus, without loss of generality we can assume that there are no hidden variables -- and the question is then just whether any 2CNF in the variables $x_1, x_2, x_3$ is logically equivalent to $x_1\lor x_2\lor x_3$.

We can easily see that this is not the case. Any nontrivial 2-clause will be true for at most $6$ of the $8$ different truth valuations of $x_1, x_2, x_3$. Taking the conjunction of several such clauses cannot make more valuations come out true -- but $x_1\lor x_2\lor x_3$ is true in $7$ cases, so it is not equivalent to any 2CNF.

Answer 2

Suppose, toward a contradiction, that we had a 2-CNF formula $\phi$, using the variables $x_1,x_2,x_3$, and some auxiliary variables $y_1,\dots,y_n$ such that, whenever we assign truth values to the $x$'s, if at least one of the three is true then we can assign values to the $y$'s to make $\phi$ true, but if all three of the $x$'s are false, then, no matter what values we give the $y$'s, $\phi$ will be false.

Choose an assignment $v_1$ of truth values to the $y$'s that makes $\phi$ true when $x_1$ is true but $x_2$ and $x_3$ are false. Similarly, choose assignments $v_2$ (resp. $v_3$) to the $y$'s that make $\phi$ true when only $x_2$ (resp. $x_3$) is true and the other two $x$'s are false. Let $v$ be the assignment of truth values to the $y$'s obtained by the majority vote of $v_1,v_2,v_3$, i.e., $v$ makes $y_i$ true iff at least two of $v_1,v_2,v_3$ make $y_i$ true.

By our assumption, if we give all three $x$'s the value false and give the $y$'s values according to $v$, then $\phi$ is false. So, as $\phi$ is a 2-CNF formula, one of the conjuncts in $\phi$ is false in this situation, and that conjunct is a disjunction of two literals (each of which is an $x$ or a $y$ or a negation of one of these.) Each of those two literals has, in our current truth assignment ($v$ for the $y$'s and false for the $x$'s), the same truth value as in at least two of the three earlier truth assignments ($v_i$ for the $y$'s and only $x_i$ true among the $x$'s). So at least one of those three earlier assignments agrees with the current one on both of the literals in the conjunct under consideration. Thus, at least one of the three earlier truth assignments falsified that conjunct and therefore falsified $\phi$. That contradicts how we chose those earlier assignments.