75 views
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.
| 75 views
0

Ans is A and D.

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.

by Boss (27.4k points)
selected by
0

Deepak , I have one doubt.. P=NP implies P  ⊆ NP and NP ⊆ P...and  PNP 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

0
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$.
0
Deepak , I have one doubt.. P=NP implies P  ⊆ NP and NP ⊆ P...and  P ≠ Nimplies 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.

0

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

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