Clique is hard to approximate within n1−ε

Abstract

We prove that, unless any problem in NP can be solved in proba-bilistic polynomial time, for any > 0, the size of the largest clique in a graph with n nodes is hard to approximate in polynomial time within a factor n 1. This is done by constructing, for any Æ> 0, a proba-bilistically checkable proof for NP which uses logarithmic randomness and Æ amortized free bits. Warning: Essentially this paper has been published in Acta Matehmatica and is subject to copyright restrictions. In particular it is for personal use only. 1