GATE CS 2012 Q4 — Regular and Context-free Languages

To determine which statement is true under the assumption that $\textsf{P} \neq \textsf{NP}$, let us analyze the relationship between these complexity classes:

By definition, a language $L$ is $\textsf{NP-complete}$ if:

1. $L \in \textsf{NP}$
2. For every language $L' \in \textsf{NP}$, $L' \le_{\textsf{P}} L$ (i.e., $L'$ is polynomial-time reducible to $L$).

Analyzing Option B: $\textsf{NP-complete} \cap \textsf{P} = \emptyset$

Suppose there exists some language $L$ such that $L \in \textsf{NP-complete} \cap \textsf{P}$.

• Since $L \in \textsf{P}$, there exists a polynomial-time algorithm to decide $L$.
• Since $L \in \textsf{NP-complete}$, every language $L' \in \textsf{NP}$ can be reduced to $L$ in polynomial time ($L' \le_{\textsf{P}} L$).
• Since we can reduce any $L' \in \textsf{NP}$ to $L$ in polynomial time, and $L$ itself can be solved in polynomial time, we can solve any $L' \in \textsf{NP}$ in polynomial time. This implies $\textsf{NP} \subseteq \textsf{P}$.
• Since $\textsf{P} \subseteq \textsf{NP}$ always holds, this would mean $\textsf{P} = \textsf{NP}$.

However, we are given that $\textsf{P} \neq \textsf{NP}$. Therefore, by contradiction, no such language $L$ can exist. Thus, $\textsf{NP-complete} \cap \textsf{P} = \emptyset$. This statement is TRUE.

Analyzing the other options:

• Option A ($\textsf{NP-complete} = \textsf{NP}$): False. If $\textsf{P} \neq \textsf{NP}$, then any problem in $\textsf{P}$ (e.g., Minimum Spanning Tree) is in $\textsf{NP}$ but cannot be in $\textsf{NP-complete}$ (otherwise $\textsf{P} = \textsf{NP}$).
• Option C ($\textsf{NP-hard} = \textsf{NP}$): False. $\textsf{NP-hard}$ contains problems that are not even in $\textsf{NP}$ (for example, the Halting Problem, which is undecidable).
• Option D ($\textsf{P} = \textsf{NP-complete}$): False. Since $\textsf{P} \neq \textsf{NP}$, their intersection is empty, so they cannot be equal.