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

CC BY-SA 3.0
2012-05-01T16:17:11.227Z
in fact in the PCP theorem and in applications to hardness of approximation, the number of queries is constant.
Sasho Nikolov
CC BY-SA 3.0
2012-05-01T16:41:00.147Z
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?
Nilesh
CC BY-SA 3.0
2012-05-01T16:42:08.850Z
@SashoNikolov That is true, though in the PCP definition an adaptive verifier can have non-constant number of queries.
Nilesh
CC BY-SA 3.0
2012-05-01T18:35:28.137Z
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.
Henry Yuen
CC BY-SA 3.0
2012-05-01T20:46:29.177Z
It seems your worries come from definition 11.4 which says that the verifier needs to run in randomized polynomial time. Polynomial in what is not well specified, but one can assume that polynomial means polynomial in $n$, $r(n)$ and $q(n)$, otherwise the definition is vacuous.
Sasho Nikolov
CC BY-SA 3.0
2012-05-02T01:51:00.457Z
@SashoNikolov The verifier is a PTM, input is of length $|x| = n$ and the proof-string is of length $q(n)2^{r(n)}$. The PTM is polytime in $n$. I don't see why that is vacuous? I did not find any definition of PCP where they say that the verifier running time is polynomial in $n, r(n), q(n)$.
I think, like Henry said, there is an implicit assumption that $q(n)$ is constant/logarithmic in $n$, otherwise there is no polytime non-adaptive verifier and by definition no PCP.
Nilesh
CC BY-SA 3.0
2012-05-02T02:13:25.630Z
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.
Henry Yuen
CC BY-SA 3.0
2012-05-01T06:46:54.893Z
2012-05-01T06:46:54.893Z
Henry Yuen
<p>So this is a question from Arora, Barak textbook which was on our homework. I submitted it so no worries. :)</p>

<p>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) &lt; t(n)$ always hold?</p>

<p>Thanks,</p>

<p>Nilesh.</p>

<cc.complexity-theory><pcp>
Non adaptive PCP
Nilesh
# Non adaptive PCP

(Asked by: username_0 on 2012-05-01)

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.

**Tags:** cc.complexity-theory, pcp

---

## 1 answers

### Answer by username_1 on 2012-05-01. Score: 3

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

> **Comments:**
> **username_2**: in fact in the PCP theorem and in applications to hardness of approximation, the number of queries is constant.  
> **username_0**: 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?  
> **username_0**: @SashoNikolov That is true, though in the PCP definition an adaptive verifier can have non-constant number of queries.  
> **username_1**: 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.  
> **username_2**: It seems your worries come from definition 11.4 which says that the verifier needs to run in randomized polynomial time. Polynomial in what is not well specified, but one can assume that polynomial means polynomial in $n$, $r(n)$ and $q(n)$, otherwise the definition is vacuous.  
> **username_0**: @SashoNikolov The verifier is a PTM, input is of length $|x| = n$ and the proof-string is of length $q(n)2^{r(n)}$. The PTM is polytime in $n$. I don't see why that is vacuous? I did not find any definition of PCP where they say that the verifier running time is polynomial in $n, r(n), q(n)$. I think, like Henry said, there is an implicit assumption that $q(n)$ is constant/logarithmic in $n$, otherwise there is no polytime non-adaptive verifier and by definition no PCP.  
> **username_1**: 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.  

---

