# If P != NP, then 3-SAT is not in P

I hope I'm in the right section:

I know that if P = NP, then 3-SAT can be solved in P (Cook), but is the opposite valid, too? If P != NP, then 3-SAT is not in P?

Thanks!

• Have you tried applying the definitions for a formal proof?
– Raphael
Jun 10, 2014 at 12:04
• By way of definition of P, NP and NP-Complete (which 3SAT is part of), the rest follows. Maybe you want to ask sth different? Jun 10, 2014 at 19:17

The opposite is valid.

$3SAT$ is an $NP$-complete problem, so every problem in $NP$ can be reduced to $3SAT$.

If $P \neq NP$ and $3SAT \in P$, every problem in $NP$ would be in $P$, contradicting $P \neq NP$. So if $P \neq NP$ then $3SAT \notin P$.

• That's what the question says?
– Raphael
Jun 10, 2014 at 12:04

Mike's proof is correct. I just wanted to add some other details.

Cook's theorem (or Cook-Levin theorem) says that there exists a polynomial time reduction from all problems in $NP$ to $SAT$ (3-$SAT$ or k-$SAT$ with $k>2$ since 2-$SAT$ is in $P$).

More specifically, it states that 3-$SAT$ is $NP$-complete.

Here is the definition that Sipser gives in his Introduction to the Theory of Computation (p. 276) of NP-completeness:

A language B is NP-complete if it satisfies two conditions:
1. B is in NP, and
2. every A in NP is polynomial time reducible to B


If $P\neq NP$, then it means that there is at least one language in $P$ that is not in $NP$. Assume 3-$SAT\in P$ (to get a proof by contradiction), the Cook-Levin theorem says that such a language (in $P$ but not in $NP$) cannot be in $NP$ without being polynomial-time reducible to $NP$-complete. This leads to a contradiction from the definition of $NP$-complete. Therefore if $P\neq NP$, 3-$SAT$ is not in $P$.

You can draw Venn diagrams for this...

Furthermore, you can note that the Berman-Hartmanis conjecture states that if one-way functions exist, then there is a language in $NP$ that cannot be polynomially reduced to $NP$-complete.