Problem Detail:
Show that proving 2SAT is not NP-Complete would prove that 3SAT is not in P.
Or eqivalently –
Show that proving 3SAT is in P would prove that 2SAT is NP-Complete.
I can see there is an easy reduction from 2SAT to 3SAT and it seems like it is the key here, but I can’t quite prove the statement above. Can anyone help?
Asked By : Ben Danon
Answered By : Chris Jefferson
This is (sort of) a trick question. This is not about a connection between 2SAT and 3SAT, it is that if 3SAT is in P, then anything which is in NP and has at least one true instance and one false instance becomes NP-complete! Let’s imagine that we are in a world where 3SAT is in P. Now consider the simple problem 1-VAR-SAT, which is SAT where we have one variable, and at most two clauses. There are 3 1-VAR-SAT problems, $x$, $!x$, and $x vee !x$. The last is the only unsolvable one. Turns out, if 3SAT is in P, then 1-VAR-SAT is NP-complete! Here is the model. Take a 3SAT instance, and solve it (that’s polynomial time, 3SAT is in P). If the problem is solvable, output $x$. If it is unsolvable, output $x vee !x$. We have turned a 3SAT instance into a 1-VAR-SAT problem, which is solvable if and only if the original is solvable, in polynomial time!
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/40390
