So this is a question from Arora, Barak textbook which was on our homework. I submitted it so no worries. :)

The question asks us to simulate an adaptive PCP with a non-adaptive one. It says this can be done in $2^{q}$ non-adaptive queries. But in that case, how can the verifier be poly-time because it now reads exponential number of proof bits? Shouldn't $q(n) < t(n)$ always hold?

Thanks,

Nilesh.

The assumption is that the number of queries is at most logarithmic in the input size ($n$), so $2^q$ is still polynomial in $n$.
• Nilesh, technically, you don't have to have a PCP with $O(\log n)$ queries; the theorem that you can convert an adaptive PCP to a non-adaptive one with $2^q$ queries is true nonetheless. You're right, when $q = \omega(\log n)$, this requires a superpolynomial-time verifier -- but that doesn't contradict the theorem. May 1, 2012 at 18:35