# Satisfiability 2 CNF-SAT to 3 CNF-SAT transformation/reduction

This Reduction is trying to prove that 2CNF-SAT is also NP-Complete, after proving 3CNF-SAT is NP-Complete.

If we had a reduction that given an instance of 2CNF-SAT with k clauses over 'i' number of variables, and we create an instance of 3CNF-SAT with 2n clauses by introducing for clause i a new variable y; then for the i'th 2SAT clause we generate two 3SAT clauses. This is a reduction from a 2CNF-SAT to a 3CNF-SAT.

Is this not a correct reduction because all of the other clauses after the transformation are still 2CNF-SAT except for the i'th clause?

• It's not clear what you are asking. You ask "is this not a correct reduction", but that depends on which problem you are trying to reduce to which other one. Please edit the question to clarify what your question is and what you're trying to achieve. Thank you! – D.W. May 1 '16 at 18:02
• What is meant with the letter "i" in your reduction is that for every clause $C_i$ we have to create two 3-SAT clauses. Example: we have a clause: $(x_1 \vee x_2)$ , we create two clauses: $(x_1 \vee x_2 \vee x_3) \wedge (x_1 \vee x_2 \vee \neg x_3)$ . Because you can only satisfy one of the two clauses by setting $x_3$ to true or false, you need to set to true one of the literals of the original clause – rotia May 2 '16 at 22:38
• The reduction is correct but it's "direction" is wrong: in order to show that 2CNF-SAT is NP-complete you must reduce it TO 3CNF-SAT (which is NP-complete). You must start with an arbitrary 3CNF-SAT $\varphi$ formula and build (in polynomial time) a 2CNF-SAT formula $\varphi'$ such that $\varphi$ is satisfiable if and only if $\varphi'$ is satisfiable. In other words: if I'm able to solve efficiently 2CNF-SAT then I would be able to solve efficiently 3CNF-SAT using such transformation. – Vor Jun 1 '16 at 13:35