5
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ I believe 2SAT is in P because each clause can be treated as a logical implication whereas 3SAT cannot be. $\endgroup$ – Ryan Mar 13 '15 at 15:16
7
$\begingroup$

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!

$\endgroup$
  • 1
    $\begingroup$ Welcome! The more general point here is that every nontrivial problem in P is P-complete under polytime many-one reductions, since you can solve the problem in the reduction. (By "nontrivial", I mean that there's at least one yes instance and at least one no instance). So, if P=NP then almost anything in NP is NP-complete (but note that this is far from the same thing as "almost anything becomes NP-complete": you should probably edit to fix that erroneous claim). $\endgroup$ – David Richerby Mar 13 '15 at 17:24
  • $\begingroup$ Thanks, you are right in particular that I was wrong about 'everything becoming NP-complete'! $\endgroup$ – Chris Jefferson Mar 13 '15 at 17:54
  • $\begingroup$ @DavidRicherby is 2SAT p-complete? $\endgroup$ – Turbo May 19 '17 at 8:28
  • $\begingroup$ @Turbo Why do you need me to look that up for you? $\endgroup$ – David Richerby May 19 '17 at 8:35
  • 1
    $\begingroup$ @Turbo You need to check what kind of reduction is being used. Polynomial-time reductions don't make sense when discussing NL because, then, the reductions are more powerful than the problems you're trying to reduce between. If you want to ask a new question, please ask a new question, rather than doing it in the comments. $\endgroup$ – David Richerby May 19 '17 at 8:38
5
$\begingroup$

Another way to put it:

  • 2-SAT is in P and in NP.
  • if any problem in P (or in NP) is not NP complete, then P!=NP.
  • so if 2-SAT is not NP-complete, then P!=NP.
  • if P!=NP, then NP-complete problems are not in P.
  • so if 2-SAT is not NP-complete, then P!=NP and 3-SAT (being NP-complete) is not in P

equivalently (easier):

  • 3-SAT is NP-complete.
  • if an NP-complete problem is in P, then P=NP.
  • if P=NP, then every problem in P is NP-complete.
  • 2-SAT is in P (and in NP).
  • so if 3-SAT is in P, then P=NP and every P (and NP) problem is NP-complete, including 2-SAT.
$\endgroup$
2
$\begingroup$

Hint: If 3SAT is in P then P=NP and so every non-trivial problem in NP is NP-complete. (Non-trivial means that it's not the empty language nor the complete language.)

$\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.