Assuming P ≠ NP, which of the following is true?

2021

Assuming P ≠ NP, which of the following is true?

  1. A.

    NP-complete = NP

  2. B.

    NP-complete ∩ P = ∅

  3. C.

    NP-hard = NP

  4. D.

    P = NP-complete

  5. 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.

Explore the full course: Up Lt Grade Assistant Teacher 2025