1
$\begingroup$

This Reduction is trying to prove that 2CNF-SAT is also NP-Complete, after proving 3CNF-SAT is NP-Complete. Why is this reduction wrong?

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.

Is this not a correct reduction because you're transforming an unknown problem into a known problem?

$\endgroup$
0
$\begingroup$

The issue is we know no polynomial time algorithm to solve a general 3CNF. There are definitely subsets of 3CNFs (like the transformed 2CNFs you describe) which are amenable to polynomial time algorithms.

As an analogy, we say that there is no algebraic formula for the roots of a general quintic polynomial. However, any quadratic can be seen as a quintic with some coefficients set to zero, and of course we do have the quadratic formula.

$\endgroup$

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.