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
