Question 4

By definition, a language $L$ is NP-complete if:

1. $L \in \text{NP}$, and
2. Every language $A \in \text{NP}$ is polynomial-time reducible to $L$ ($L$ is NP-hard).

If any NP-complete problem belongs to $\text{P}$, then by the closure under polynomial-time reduction, every problem in $\text{NP}$ would also be in $\text{P}$, which would imply $\text{P} = \text{NP}$.

Therefore, under the hypothesis that $\text{P} \ne \text{NP}$:

Evaluating the given options:

• (A) $\text{NP-complete} = \text{NP}$: False (there exist problems in $\text{NP}$ that are not NP-complete, such as problems in $\text{P}$).
• (B) $\text{NP-complete} \cap \text{P} = \emptyset$: TRUE.
• (C) $\text{NP-hard} = \text{NP}$: False (NP-hard includes undecidable problems).
• (D) $\text{P} = \text{NP-complete}$: False.

Hence, option (B) is correct.