Why it is nearly impossible to have an approximation algorithm for Maximum Clique problem?

I read a theorem which states that:
If there exists a polynomial time approximation algorithm for solving the Maximum Clique problem (or the Maximum Independent Set problem) for any constant performance ratio r, then NP = P.

But I never understood the reasoning behind this!!

In fact, something stronger is true: if you can approximate maximum clique within $n^{1-\epsilon}$ for some $\epsilon > 0$ then P=NP. This is because for every $\epsilon > 0$ there is a polytime reduction $f_\epsilon$ that takes an instance $\varphi$ of SAT and returns an instance $(G,cn)$ of maximum clique such that:

• If $\varphi$ is satisfiable then $G$ has a $cn$-clique.

• If $\varphi$ is not satisfiable then $G$ has no $cn^{1-\epsilon}$-clique.

If you could approximate maximum clique within $n^{1-\epsilon}$ you would be able to distinguish the two cases (exercise), and so to decide whether $\varphi$ is satisfiable or not.

The reduction uses the PCP theorem as a first ingredient. Given the PCP theorem it is not hard to give a similar reduction with a constant gap, and with some effort to give a reduction with a gap of $n^\epsilon$ for some $\epsilon > 0$. The reduction claimed above, which has a gap of $n^{1-\epsilon}$ for every $\epsilon>0$, is much harder. See lecture notes of Guruswami and O'Donnell for the constant gap, and lecture notes of Scheideler for the $n^\epsilon$ gap.

StackExchange Computer Science Q#50634, answer score: 9