Why it is nearly impossible to have an approximation algorithm for Maximum Clique problem?
In fact, something stronger is true: if you can approximate maximum clique within $n^{1-\epsilon}$ for some $\epsilon &gt; 0$ then P=NP. This is because for every $\epsilon &gt; 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 &gt; 0$. The reduction claimed above, which has a gap of $n^{1-\epsilon}$ for every $\epsilon&gt;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.