Free Bits, PCPs and Non-Approximability

by Mihir Bellare, Oded Goldreich and Madhu Sudan

Abstract

A breakthrough in the study of the complexity of approximation came about with the reduction of Feige et. al. (FGLSS) which translates PCP systems (for NP) into NP-hardness approximation results for MaxClique. We show that PCP systems are inherent to the study of approximation, and in particular amortized free-bits capture the hardness factor for MaxClique. Specifically, the following two (loosely stated) conditions are equivalent:
(1) MaxClique is NP-hard to approximate to within $N^(1/(1+f))$ factor;
(2) NP has PCP systems of logarithmic randomness and amortized free-bit complexity $f$.

We also introduce new machinery (most notably the Long-Code) for the construction of PCP systems, yielding improvements in all investigated parameters of PCP systems for NP. In particular, we obatain,

• PCP systems for NP, of logarithmic randomness and 2 amortized free-bits.
  Thus MaxClique is NP-hard to approximate within yields a $N^(1/3)$ factor.
• Simple PCP systems for NP leading to substantial improvements in the hardness results for several popular MaxSNP problems such as Max3SAT, Max2SAT, MaxCUT and MinVertexCover.

Finally, we initiate a systematic study of properties of PCP systems and transformation among them.

Versions

• 1st version, May 1995. (Not avialable - superseded by 2nd version.)
• FOCS'95 version. (160KB)
• 2nd version, August 1995. (126 pages, 1.2 MB)
• 3rd version, December 1995. (128 pages, 1.2 MB)
  Starting with this version, our best results for PCP and non-approximability of MaxSNP problems are obtained via a new adaptive codeword test (and the induced new verifier).
• 4th version, December 1996. (127 pages, 1.2 MB)
  Corrects a (resticted in scope) error in previous versions.
• 5th version, July 1997. (120 pages, 1.2 MB) [PDF]
  Significant re-organization of previous versions.
• Final version in SICOMP, Vol. 27, No. 3, pages 804-915, June 1998.