Key points are not available for this paper at this time.
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
Johan Håstad (Fri,) studied this question.