IIT Kanpur

Question

7. Which of the following statements are known to be true.
 A. P is a subset of NP.
 B. NP is a subset of P.
 C. P is not a subset of NP.
 D. NP is not a subset of P.

Comments

Ans is A and D.

ref: https://goo.gl/images/hqrzw6

Answer 1

Answer is ONLY A.

There maybe Two scenarios :

1. If $P = NP$ then A and B will be True. 

2. If $P \neq NP$ then A and D will be True.

Thus, Since it is NOT known whether $P = NP$ or Not. So, We can derive one thing for sure that P is a subset of NP for sure whatever be the case ($P = NP$ or Not)

---

Saying P is a Proper subset of NP would again be wrong. 

---

Comments

Deepak , I have one doubt.. P=NP implies P  ⊆ NP and NP ⊆ P...and  P ≠ NP implies P  ⊂ NP...So ,I think  from these 2 things , we can only say P  ⊂ NP..ie. P is a proper subset of NP , not P is subset of NP...Please correct me where I m wrong

---

Take Contradiction Approach to see this. Let's say P is a Proper Subset of NP. Now take the case of "If $P = NP$, Now saying P is a Proper subset of NP would be wrong. But Still, Saying P is a Subset of NP is still correct Because A set is always a Subset of itself (But a set is never a Proper Subset of Itself).

If $P \neq NP$ then We can say both statements " Proper Subset" and "Subset". So, Saying "Just Subset" is True in both cases But Saying Proper Subset would be wrong, has been $P = NP$.

---

Deepak , I have one doubt.. P=NP implies P  ⊆ NP and NP ⊆ P...and  P ≠ NP implies P  ⊂ NP...So ,I think  from these 2 things , we can only say P  ⊂ NP..ie. P is a proper subset of NP , not P is subset of NP...

The reason why You got confused is the definition of "Set Equality" which You used i.e. P  ⊆ NP and NP ⊆ P

(It is indeed a correct definition) And From this definition and P  ⊂ NP, You took what is Common and the common thing that you  found was "⊂". But it is wrong. Because What You should have considered was "P  ⊆ NP and NP ⊆ P" But You only considered "P  ⊆ NP". 

There is Nothing common between "Set Equality" and "Proper Subset". Both are Mutually Exclusive and Exhaustive.  But The Term "Subset" can be used for Both.

---

@Deepak ,Thank you ! ..Actually , I have written wrong.  correct statement should be

"P ≠ NP implies P  ⊂ NP  and P ⊆ NP both "