Lesson 3

It turns out that such a probabilistically checkable proof exists for every problem in the class NP and there is even a short such proof. To verify that this is (with high probability) indeed a proof of membership in the language, it is enough to read a constant number of bits from it and for this, a logarithmic number of random bits is sufficient (from which it follows that the size of such a proof is polynomial): \(NP=PCP(O(\log n), O(1))\).

From the PCP theorem, one can also derive results about the inapproximability of NP-hard problems. For example, it is known that there exists a constant \(0 < \alpha < 1\) such that the existence of an \(n^{\alpha}\)-approximation algorithm for the independent set problem implies that P\(=\)NP. Here, an \(n^{\alpha}\)-approximation means an algorithm that finds an independent set in polynomial time, the size of which is at most \(n^{\alpha}\) times smaller than the optimal one.