Assuming P ≠ NP, which of the following is true?
2021
Assuming P ≠ NP, which of the following is true?
- A.
NP-complete = NP
- B.
NP-complete ∩ P = ∅
- C.
NP-hard = NP
- D.
P = NP-complete
- E.
Question not attempted
Attempted by 94 students.
Show answer & explanation
Correct answer: B
Under the assumption that P ≠ NP, we analyze each option:
Option A: NP-complete = NP. This is incorrect because NP-complete problems are a subset of NP, and not all problems in NP are NP-complete. If NP-complete = NP, it would imply that every problem in NP is NP-complete, which is not true under P ≠ NP.
Option B: NP-complete ∩ P = ∅. This is correct because if any NP-complete problem were in P, then P = NP, contradicting the assumption. Therefore, no NP-complete problem can be in P.
Option C: NP-hard = NP. This is incorrect because NP-hard problems include problems that are not in NP, such as the halting problem. Thus, NP-hard is a broader class than NP.
Option D: P = NP-complete. This is incorrect because it would imply that all NP problems can be solved in polynomial time, meaning P = NP, which contradicts the assumption.
Option E: Question not attempted. This is a placeholder and does not represent a valid computational statement.
Therefore, the only true statement under P ≠ NP is Option B.