Why does PCP theorem imply that NP problems are hard to approximate?

Question

What I only got currently from PCP theorem is that it needs at most $O(\log n)$ randomness and $O(1)$ query of proof to approximate. So how does this result relate to the fact that solution to NP problems are hard to approximate?

Answer 1

Take as an example SAT. The PCP theorem (in one formulation) shows that there is a PCP for SAT which uses $O(\log n)$ bits of randomness, queries $O(1)$ places, always accepts on YES instances, and rejects on NO instances with probability at least $\alpha > 0$. The PCP queries at most $2^{O(\log n)} = n^{O(1)}$ different locations in the proof, so the entire proof can be encoded in polynomial size. For each of the $2^{O(\log n)}$ possible queries, we can write a formula of constant size that is true if and only if the verifier accepts. Taking all these formulas together in CNF form, we get a CNF $\psi$ (which depends on the instance of SAT) on polynomially many variables (representing the bits of the proof) with polynomially many clauses (each possible query gives rise to $O(1)$ many clauses).

By the definition of PCP, for each $\phi \in \mathrm{SAT}$, there is a proof that satisfies the verifier on all possible queries. In other words, $\psi$ is satisfiable. On the other hand, for each $\phi \notin \mathrm{SAT}$, every proof is rejected with probability at least $\alpha$. This means that any assignment satisfies at most $1-\alpha/O(1)$ of the clauses of $\psi$, the $O(1)$ factor coming from the fact that the result of each query is encoded using $O(1)$ different clauses, one of which must be falsified if the query leads to rejection by the verifier.