0
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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$.

$\endgroup$
7
  • 1
    $\begingroup$ in fact in the PCP theorem and in applications to hardness of approximation, the number of queries is constant. $\endgroup$ – Sasho Nikolov May 1 '12 at 16:17
  • $\begingroup$ Thanks for the responses! @Henry I cannot find that assumption in the question (11.2 in the book) or the definition of PCP (section 11.2, def 11.4 in the book). Did I miss it somewhere? $\endgroup$ – Nilesh May 1 '12 at 16:41
  • $\begingroup$ @SashoNikolov That is true, though in the PCP definition an adaptive verifier can have non-constant number of queries. $\endgroup$ – Nilesh May 1 '12 at 16:42
  • 1
    $\begingroup$ 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. $\endgroup$ – Henry Yuen May 1 '12 at 18:35
  • 1
    $\begingroup$ At the risk of belaboring the issue: in the literature and in research, PCP verifiers are almost always considered to run in polynomial time (in the input length). However, it is perfectly reasonable to define PCPs more generally, not insisting on this polynomial time condition. One could then consider PCP verifiers that run in, say, subexponential time. I don't know if this is an interesting concept, but one could consider it nonetheless. It just so happens we usually only consider polytime verifiers. $\endgroup$ – Henry Yuen May 2 '12 at 2:13

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.