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?

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

3 Answers 3


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!

  • 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$ Commented Mar 13, 2015 at 17:24
  • $\begingroup$ Thanks, you are right in particular that I was wrong about 'everything becoming NP-complete'! $\endgroup$ Commented Mar 13, 2015 at 17:54
  • $\begingroup$ @DavidRicherby is 2SAT p-complete? $\endgroup$
    – Turbo
    Commented May 19, 2017 at 8:28
  • $\begingroup$ @Turbo Why do you need me to look that up for you? $\endgroup$ Commented May 19, 2017 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$ Commented May 19, 2017 at 8:38

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.
  • $\begingroup$ "if P=NP, then every problem in P is NP-complete." are you sure about this statement? This would mean that also every problem in NL or AC0 woulr be NP-complete (since every member such classes does also belong to P). $\endgroup$
    – logi-kal
    Commented May 15, 2023 at 11:54
  • $\begingroup$ @logi-kal You are correct. The class P includes trivial problems, whereas NP-complete does not. The argument needs a modification, but would still stand corrected. I think classes like NL would still be NP-complete if P=NP, because NP-complete problems can be polynomially reduced to them. $\endgroup$ Commented May 15, 2023 at 13:46

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.)


Your Answer

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

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