After many improvements to these results it is now known that, for every real number ε > 0, there can be no polynomial time algorithm that approximates the maximum clique to within a factor better than O(n1 − ε), unless P = NP.
După mai multe îmbunătățiri ale acestor rezultate, se cunoaște că, pentru orice număr real ε > 0, nu poate exista un algoritm în timp polinomial care aproximează clica maximă cu un factor mai bun decât O(n1 − ε), decât dacă P = NP.