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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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$.

Improve this answer
$\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, 2012 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, 2012 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, 2012 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, 2012 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, 2012 at 2:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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