In this section, we give an outline of the proof of the PCP-Theorem, which states that NP=PCP(logn,1). The key idea for reducing the number of random bits, which also implies a reduction of the length of the proof, is a more concise encoding of an assignment. Instead of linear functions we use multivariate polynomials of low degree as an encoding. We will refer to such an encoding based on multivariate polynomials as the polynomial code. In this case the length of such an encoding will be polynomially related to the size of the given Boolean formula.
['Volker Heun', 'Wolfgang Merkle', 'Ulrich Weigand']
Proving the PCP-Theorem