3
$\begingroup$

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$

$\endgroup$
  • $\begingroup$ If $P\neq NP$, then this isn't possible - if you could express $x_1\lor x_2\lor x_3$ as 2SAT-CNF, so you could any clause with three literals, and by conjuncting you could get from any 3SAT instance to a 2SAT instance in linear (I believe) time. This makes me believe there should be an easy proof that such clause is not equivalent to any 2SAT-CNF formula. $\endgroup$ – Wojowu Dec 6 '15 at 20:54
  • $\begingroup$ Now, if such an encoding would have been proven not to exist, wouldn't that have proven $P\neq NP$ too, as then there couldn't possibly be a poly-time reduction from 3SAT to 2SAT? $\endgroup$ – MonadBoy Dec 6 '15 at 21:25
  • 2
    $\begingroup$ @A.Sh: No, because a poly-time reduction from 3SAT to 2SAT does not necessarily have to proceed by encoding each clause separately. $\endgroup$ – hmakholm left over Monica Dec 6 '15 at 21:27
  • $\begingroup$ Ah, ok. Thanks for straightening that out, Henning. $\endgroup$ – MonadBoy Dec 6 '15 at 21:28
3
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Nice - this resolution process makes it clear $\endgroup$ – user2183977 Dec 6 '15 at 21:37
  • $\begingroup$ This has sparked my curiosity: This proof does show that there is no Karp reduction from 3SAT to 2SAT, as there is a tiny subset of the former that is inexpressible in the latter. Assuming that all other 3SAT formulae are somehow expressible as 2SAT formulae, one could avoid the $P\neq NP$ scenario by checking the number of clauses first, and then proceeding with brute-force, if just one clause, or some poly-time algorithm in the case of more than one clause. In this way, $P\neq NP$ is avoidable. Are there any examples of bigger 3SAT formulas that aren't representable as 2SAT formulas? $\endgroup$ – MonadBoy Dec 6 '15 at 21:50
  • $\begingroup$ @A.Sh: I don't understand where you get "tiny subset" here. Most 3SAT problems won't be representable as 2SAT ones. $\endgroup$ – hmakholm left over Monica Dec 6 '15 at 22:01
  • $\begingroup$ I meant "tiny subset" as in there being quite a lot of 3SAT formulas with more than one clause (relatively speaking) compared to ones with one clause only. A bit informally stated, but I hope the point comes across. Your proof shows that 3SAT formulas of one clause cannot be represented as 2SAT formulas, and I didn't assume anything about the other ones when writing that comment. Do you, by "most", mean that there are many more 3SAT formulas that cannot be represented as 2SAT ones? $\endgroup$ – MonadBoy Dec 6 '15 at 22:07
  • $\begingroup$ Also, why doesn't this (again, out of curiosity) imply that $P\neq NP$ (I'm somewhat confident it doesn't)? If we assume $P=NP$, then all problems in $NP$ are also $NP$-complete. In that case, there must be a Karp-reduction from 3SAT to 2SAT. But this is proven not to be the case, as there are 3SAT formulas inexpressible as 2SAT formulas. Hence we have a contradiction. I assume something is wrong with that "proof", but I cannot see what. $\endgroup$ – MonadBoy Dec 6 '15 at 22:13
1
$\begingroup$

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.

| cite | improve this answer | |
$\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.