Problem Detail: I am not a formally trained guy on Complexity theory, but due to interest I am learning it. Based on different feedbacks, I have started my journey with Micheal Sipser’s “Theory of Computation” (2013 edition). My question is based upon some statements from the book. My sincere apologies if the question is meaningless. Here it goes:
- On page 298, it is written as “We are unable to prove the existence of a single language in NP that is not in P”. That implies all the NP languages are also in P.
- Theorem 7.27 says $SATin P$ iff $P=NP$, and it’s an implication in both directions.
- From cook’s theorem, $SAT$ is NP-complete. Hence, from the NP-complete definition $SAT in NP$.
- Now, from the point 3 and 1, as $SAT in NP$ it should also be $SAT in P$, and therefore from point 2 it should be $P=NP$.
I got stuck here, I know there is some flaw in this logical deduction (because it is not that easy to prove), but I am unable to find it. Please help me in understanding this concept, so that I can proceed further. Thanks in advance.
Asked By : Brainy
Answered By : lPlant
The important point is the iff, it means if and only if. Point 2 should be read as SAT is an element of $P$ if and only if $P=NP$, and we do not know if $SAT$ is in $P$. Also, point one does not say all languages in $NP$ are in $P$, just that we have not proven that one is not. So Just because $SAT$ is in $NP$ does not mean it is necessarily in $P$. A proof of a language as he describes would prove $P neq NP$
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/28285 Ask a Question Download Related Notes/Documents
