# Alphabet Reduction Step in PCP Proof

I understand that the purpose of the alphabet reduction step in Dinur's proof of the PCP theorem is to reduce the alphabet after the graph powering stage. However, I don't see why the alphabet needs to be reduced- it is still a constant (though larger), and it seems that the graph powering step can be reapplied even with a larger alphabet size. Since the process is repeated logarithmically many times, the ending alphabet size will be polynomial in the input size. Please let me know what I am missing.

• Dec 15, 2010 at 4:27

And if I am not mistaken, the alphabet size increases from $\left|\Sigma\right|$ to $\Omega(\left|\Sigma\right|^c)$ for some constant $c$ in each graph powering step. If you do not make the alphabet reduction in middle steps, the alphabet size will blow up exponentially within a logarithmic number of iterations.
• Yes but it also depends on the alphabet size. You need to read $\Theta(\log\left|\Sigma\right|)$ bits to get the value of each variable. So NP-hardness of gap-CSP is equivalent to the PCP theorem when $\left|\Sigma\right|$ is independent of the input length $n$, which is usually implicit in many references.