0
$\begingroup$

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

$\endgroup$
1
  • 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
    Commented Aug 18, 2017 at 23:11

1 Answer 1

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

$\endgroup$
4
  • $\begingroup$ But what is the proof then? $\endgroup$ Commented Aug 19, 2017 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
    Commented Aug 19, 2017 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
    Commented Aug 19, 2017 at 9:53
  • $\begingroup$ The proof that the answer to my question is positive is by the definition of equisatisfiable, am I right? $\endgroup$ Commented Aug 19, 2017 at 15:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.