Does every 3CNF propositional formula has an equisatisfiable 2CNF propositional formula?
$\begingroup$
$\endgroup$
1
asked Aug 18 '17 at 22:46
-
2$\begingroup$ There are satisfiable 2SAT instances and not. There are satisfiable 3SAT instances and not. I think that validity of formula $\exists f\forall g: 2SAT(f)=3SAT(g)$ is not hard to evaluate. $\endgroup$ – rus9384 Aug 18 '17 at 23:11
Add a comment
|
$\begingroup$
$\endgroup$
4
Yes. If the 3CNF formula is satisfiable, here is an equisatisfiable 2CNF formula: True. If the 3CNF formula is not satisfiable, here is an equisatisfiable 2CNF formula: False. So yes, every 3CNF formula has an equisatisfiable 2CNF formula.
If you want to actually find that formula in a reasonable amount of time, then we don't know of any way to find such a formula in polynomial time (existence of such a method would prove that P = NP).
-
-
2$\begingroup$ @ErezZrihen The above is a perfect proof of the existence of the equisatisfiable 2CNF. It's even a constructive proof. I don't understand what you are looking for. $\endgroup$ – chi Aug 19 '17 at 8:04
-
1$\begingroup$ But somehow it's possible to make a 2SAT with same amount of positive assignments in polynomial time or am I wrong? $\endgroup$ – rus9384 Aug 19 '17 at 9:53
-
$\begingroup$ The proof that the answer to my question is positive is by the definition of equisatisfiable, am I right? $\endgroup$ – Farewell Stack Exchange Aug 19 '17 at 15:16
