search
Log In
0 votes
139 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 139 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. 



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

0 votes
1 answer
1
702 views
What was the last rank in the waitlist group which got admission offer from IIT Kanpur last year? Is there any chance for waitlist rank of around 20?
asked May 23, 2018 in Written Exam Hakuna Matata 702 views
1 vote
1 answer
2
180 views
Are the admissions based solely on written & programming tests, or does GATE score get some weightage during final selection?
asked May 6, 2018 in Written Exam Hakuna Matata 180 views
2 votes
0 answers
3
166 views
Consider a process with a single CPU burst of 100 time units and a single disk I/O of 1000 time units at the end. If the timer interval is fifteen time units and the process scheduling algorithm is round-robin, at most how many times would the ... entering the terminated state? Assume that there is a sufficiently large number of processes of similar nature trying to run on the CPU._________
asked May 4, 2018 in Written Exam Rishabh Malhotra 166 views
0 votes
2 answers
4
224 views
An address sequence S experiences 100 compulsory cache misses. The sequence S experiences 500 misses when it is passed through a 32 KB fully-associative cache. The sequence S experiences 1000 misses when it is passed through a 32 KB 8-way set-associative cache. The number of conflict misses that the sequence S experiences when it is passed through a 32 KB 8-way set-associative cache is _________
asked May 4, 2018 in Written Exam Rishabh Malhotra 224 views
...