4
$\begingroup$

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:

  1. 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.
  2. Theorem 7.27 says $SAT\in P$ iff $P=NP$, and it's an implication in both directions.
  3. From cook's theorem, $SAT$ is NP-complete. Hence, from the NP-complete definition $SAT \in NP$.
  4. 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.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
7
$\begingroup$

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$

Improve this answer
$\endgroup$
10
$\begingroup$

You are misinterpreting the statement quoted at point 1. We are unable to prove the existence of a single language in NP that is not in P, but we suspect that there are infinitely many, in fact, we suspect that all NP-complete languages are not in P.

Improve this answer
$\endgroup$
10
  • $\begingroup$ Stating that "we suspect" something is based purely on opinion on a contested topic. "We" also suspect that no such language exists. $\endgroup$
    – lPlant
    Commented Jul 8, 2014 at 20:15
  • 2
    $\begingroup$ @IPlant No, most experts do believe that NP is different from NP. While the consensus is perhaps not as wide as in other "contested" issues, still it is reasonable to assume that this is Sipser's opinion on the subject, or even just the opinion he would recommend for a novice, considering common opinions in the area. $\endgroup$
    – Yuval Filmus
    Commented Jul 8, 2014 at 20:27
  • 3
    $\begingroup$ @TCSLearner Unfortunately, it's not that simple. A lot of work in complexity theory is done under the assumption that NP is different from P, or equivalently, that NP-hard problems are not in P. All of complexity-style cryptography is done under this assumption. You lose a lot if you assume that NP equals P. If, on the other hand, you assume that they're different, then there are many nice hardness of approximation results, matching the best known approximation algorithms. $\endgroup$
    – Yuval Filmus
    Commented Jul 9, 2014 at 1:43
  • 1
    $\begingroup$ @TCSLearner No, we don't know whether this statement is true, false, or even independent. Most of us expect it to be false, i.e. we expect there to be NP problems which are not in P. Whether a certain problem belongs to P is independent of our being able to prove or refute it. $\endgroup$
    – Yuval Filmus
    Commented Jul 9, 2014 at 14:21
  • 1
    $\begingroup$ @TCSLearner It might help the confusion to point out that we similarly know many NP-complete problems which are known to be in NP but are not known to be in P. In other words if we apply your reasoning (which appears to be: not knowing something is false is evidence that it is true), then we would both conclude that P=NP (since we do not know of any problem in NP not in P) and P!=NP (since we do not know of any NPC problem that is in P). But this just underscores the fact that such inferences don't work. $\endgroup$
    – John
    Commented Jul 10, 2014 at 17:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.