Question 30 – ISRO-2007
April 9, 2024Computer-Networks
April 9, 2024Algorithms
Question 29 |
Assuming P ≠ NP, which of the following is TRUE?
NP-complete = NP | |
NP-complete ∩ P = ∅ | |
NP-hard = NP | |
P = NP-complete |
The definition of NP-complete is,
A decision problem p is NP-complete if:
1. p is in NP, and
2. Every problem in NP is reducible to p in polynomial time.
It is given that assume P ≠ NP , hence NP-complete ∩ P = ∅ .
This is due to the fact that, if NP-complete ∩ P ≠ ∅ i.e. there are some problem (lets say problem P1) which is in P and in NP-complete also, then it means that P1 (NP-complete problem) can be solved in polynomial time also (as it is also in P class) and this implies that every NP problem can be solve in polynomial time, as we can convert every NP problem into NP-complete problem in polynomial time.
Which means that we can convert every NP problem to P1 and solve in polynomial time and hence P = NP, which is contradiction to the given assumption that P ≠ NP.
The definition of NP-complete is,
A decision problem p is NP-complete if:
1. p is in NP, and
2. Every problem in NP is reducible to p in polynomial time.
It is given that assume P ≠ NP , hence NP-complete ∩ P = ∅ .
This is due to the fact that, if NP-complete ∩ P ≠ ∅ i.e. there are some problem (lets say problem P1) which is in P and in NP-complete also, then it means that P1 (NP-complete problem) can be solved in polynomial time also (as it is also in P class) and this implies that every NP problem can be solve in polynomial time, as we can convert every NP problem into NP-complete problem in polynomial time.
Which means that we can convert every NP problem to P1 and solve in polynomial time and hence P = NP, which is contradiction to the given assumption that P ≠ NP.