GATE CS 2014 Set 1 Q38 — Turing Machines

The CLIQUE problem (finding whether a graph contains a clique of size $k$) is a well-known NP-complete problem. Finding the size of the largest clique is the optimization version of this problem.

If a polynomial-time algorithm is discovered to compute the largest clique, then the NP-complete decision version of CLIQUE can also be solved in polynomial time. This implies:

When $\text{P} = \text{NP}$, every NP-complete problem can be solved in polynomial time, meaning $\text{NPC} \subseteq \text{P}$. Since $\text{NPC}$ is already a subset of $\text{NP}$ by definition, all three classes collapse into the same set (excluding the trivial languages $\emptyset$ and $\Sigma^*$):

Thus, the correct Venn diagram must represent all three classes as identical, which corresponds to Option D.