Consider verifiers in the usual sense:

Non adaptive : reads all positions of the proof predefined

Adaptive: Reads the proof iteratively.

Many lecture notes on PCP say the following: Adaptive verifier with q queries is equivalent to non-adaptive with some q' queries where q' is a constant and both using same randomness. In other words I think this means

Non adaptive q' queries can simulate adaptive q queries. But I don't see why? How to show this?


Consider an adaptive algorithm making $q$ queries. Fixing the randomness, we can describe the positions queried by the algorithm using a function $A$ which gets as input the answers of the preceding queries, and outputs the next position to be queried. If the bits are read from an array $x$, then the adaptive algorithm works as follows:

  1. Read $b_1 = x_{A(\lambda)}$.
  2. Read $b_2 = x_{A(b_1)}$.
  3. Read $b_3 = x_{A(b_1b_2)}$.
  4. ...
  5. Read $b_q = x_{A(b_1 b_2 \ldots b_{q-1})}$.

To simulate this non-adaptively, we simply read $x_{A(w)}$ for all words $w$ of length at most $q-1$. Given these $q' = 2^q-1$ non-adaptive queries, we can simulate the adaptive algorithm.

| cite | improve this answer | |

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.