[Solved]: If P != NP, then 3-SAT is not in P

Problem Detail: 

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!

Asked By : user22709

Answered By : Mike B.

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/27566

3.2K people like this

 Download Related Notes/Documents