I have the exact same question as this guy, except I don't agree with the "verified" answer. Since in his answer the one to one mapping he describes depends on the input it makes the verifier $V'$ not a Turing machine (since it's now even worse than non uniform). If we only change the proof and the verifier in the trivial way we have to in compute in polynomial time the index of $M(x)$ in $\{M(y) ; y \in \{0;1\}^n \}$ where M is a polytime TM and it seems impossible. Therefore if the claim is true it doesn't seem that trivial (to me at least) to prove it like Arora and Barak make it out to be.

I'm sorry in advance if this kind of behavior in unallowed (regarding reposting the same question), I couldn't do anything else (like comment) due to lack of reputation.

  • $\begingroup$ Hello there. Since the queries are non adaptive, you can start by executing the old verifier $V$ with $x,r$ and find the $|q|$ indices on which it queries the proof. Now, map those indices to $\{1,...,q\}$ using some function $f$ (which you can construct during runtime) and for each index $i$ the old verifier wishes to read, ask for $\pi(r,f(i))$ instead. $\endgroup$ – Ariel Dec 3 '19 at 18:33
  • $\begingroup$ Hi, thanks for your answer. I don't think the answer is true however. Let me explain my reasonning. First on a conceptual level if we give "r" to the prover then it's easy for the prover to trip us up. As a concrete example think about the language L of pairs of non isomorphic graph and the usual way we prove it belongs to Pcp(n,1). Second your argument fails because your transformation from $\pi$ to $\pi '$ is not a bijection. So we can't argue that if there was a $\pi '$ which contradicted completeness of the new verifier then there would be a $\pi$ contradicting completeness of the old one. $\endgroup$ – PMercier Dec 4 '19 at 3:57

Your Answer

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

Browse other questions tagged or ask your own question.