2
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ 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! $\endgroup$
    – D.W. ♦
    May 1, 2016 at 18:02
  • $\begingroup$ 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 $\endgroup$
    – rotia
    May 2, 2016 at 22:38
  • 1
    $\begingroup$ 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. $\endgroup$
    – Vor
    Jun 1, 2016 at 13:35

1 Answer 1

Reset to default
2
$\begingroup$

It looks like you are trying to prove either that 2CNF-SAT is NP-Complete, or that 3CNF-SAT has a polynomial algorithm, by reducing 2SAT to 3SAT. But that's not how it goes! If you're trying to do what I think you're trying to do, then you should reduce 3SAT to 2SAT. Unfortunately, if you can reduce 3SAT to 2SAT, then that would imply P=NP, so that's probably very hard.

It's very easy to get confused about which way a reduction should go, and how you should make one. Please read my answer to this related question: Implications of Halting Problem being undecidable, in particular the 'cheat sheet' section, where I try to clear up some confusion around the topic, and let me know if you have questions after reading that, then I might edit this answer tailored specifically to whatever question you have afterwards.

Improve this answer
$\endgroup$

Your Answer

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

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