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.


The alphabet size corresponds to the query complexity of the PCP verifier. So you need to make it a constant eventually so that the PCP has constant query complexity, as stated in the PCP theorem.

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.

| cite | improve this answer | |
  • $\begingroup$ Doesn't the query complexity correspond to the arity(q)? The goal of Dinur's proof is to prove that the gap CSP problem is NP-hard, and this problem is equivalent to the PCP theorem. In the proof of this equivalence, the PCP query complexity corresponds to the arity of the CSP. $\endgroup$ – user934 Dec 15 '10 at 2:05
  • $\begingroup$ 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. $\endgroup$ – Zeyu Dec 15 '10 at 2:15
  • 1
    $\begingroup$ Put slightly differently: (1) simply repeating the powering step logarithmic times gives an exponentially large alphabet (instead of a polynomially large alphabet as stated in the question), and (2) a “PCP” with an exponentially large alphabet for NP is not meaningful because you can simply write the whole satisfying assignment as one “letter.” $\endgroup$ – Tsuyoshi Ito Dec 15 '10 at 23:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy