The Gateway to Computer Science Excellence
0 votes
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.
in Written Exam by Loyal (6.9k points) | 75 views
0

Ans is A and D.

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

1 Answer

+2 votes
Best answer

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. 


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 "

 

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,297 answers
198,265 comments
104,977 users