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

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

• 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. Commented Aug 18, 2017 at 23:11

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

• But what is the proof then? Commented Aug 19, 2017 at 2:26
• @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.
– chi
Commented Aug 19, 2017 at 8:04
• But somehow it's possible to make a 2SAT with same amount of positive assignments in polynomial time or am I wrong? Commented Aug 19, 2017 at 9:53
• The proof that the answer to my question is positive is by the definition of equisatisfiable, am I right? Commented Aug 19, 2017 at 15:16