0
$\begingroup$

Does every 3CNF propositional formula has an equisatisfiable 2CNF propositional formula?

|cite|improve this question
$\endgroup$
  • 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
3
$\begingroup$

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

|cite|improve this answer
$\endgroup$
  • $\begingroup$ But what is the proof then? $\endgroup$ – Farewell Stack Exchange Aug 19 '17 at 2:26
  • 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

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.