Question 48

1. The CLIQUE problem (determining whether a graph has a clique of size $k$) is one of Karp's 21 NP-complete problems.

2. Computing the largest clique allows one to solve the CLIQUE decision problem in polynomial time by simply checking whether the size of the largest clique is $\ge k$.

3. By definition of NP-completeness, every problem in NP polynomial-time reduces to CLIQUE. Therefore, if CLIQUE is solvable in polynomial time, then every problem in NP is solvable in polynomial time:

4. Furthermore, when $P = NP$, every non-trivial language in NP (any language other than $\emptyset$ and $\Sigma^*$) is NP-complete under polynomial-time many-one reductions.

5. Thus, the complexity classes collapse entirely to $P = NP = NPC$.

This is depicted in diagram (D), where $P = NP = NPC$.