Approximating clique is almost NP-complete
Uriel Feige, S. Goldwasser, László Lovász, Muli Safra, Márió Szegedy · 2002
The computational complexity of approximating omega (G), the size of the largest clique in a graph G, within a given factor is considered. It is shown that if certain approximation procedures exist, then EXPTIME=NEXPTIME and NP=P.>