Clique is hard to approximate within n/sup 1-ε/
Johan Håstad · 2002
The author proves that unless NP=coR, Max Clique is hard to approximate in polynomial time within a factor n/sup 1-/spl epsiv// for any /spl epsiv/>0. This is done by, for any /spl delta/>0, constructing a proof system for NP which uses /spl delta/ amortized free bits. A central lemma, which might be of independent interest, gives sufficient conditions (in the form of a certain type of agreement) for creating a global function from local functions certain local consistency conditions.