2
$\begingroup$

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!

$\endgroup$
2
  • 1
    $\begingroup$ Have you tried applying the definitions for a formal proof? $\endgroup$
    – Raphael
    Jun 10, 2014 at 12:04
  • $\begingroup$ 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? $\endgroup$
    – Nikos M.
    Jun 10, 2014 at 19:17

2 Answers 2

4
$\begingroup$

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

$\endgroup$
1
  • 1
    $\begingroup$ That's what the question says? $\endgroup$
    – Raphael
    Jun 10, 2014 at 12:04
2
$\begingroup$

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.

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