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

Key idea: if any NP-complete problem were in P, then every problem in NP would be in P.

• NP-complete problems are problems that are in NP and are NP-hard (every problem in NP reduces to them in polynomial time).

• If an NP-complete problem has a polynomial-time algorithm (i.e., lies in P), then composing reductions with that algorithm yields polynomial-time algorithms for every problem in NP, so NP ⊆ P.

• Therefore, under the assumption P ≠ NP, no NP-complete problem can be in P, and so the intersection of NP-complete and P is empty.

Conclusion: NP-complete ∩ P = ∅.