<p>I'm looking through some lectures and books to understand the PCP verifier constructed by Hastad. I noticed that the subtle difference of an adaptive or non-adaptive PCP verifier seems to correspond to verifier with perfect or non-perfect completeness.</p>

<p>In "A tight characterization of NP with 3 query PCPs" the authors point out that there are (due to Trevisan and Zwick) strong restrictions using non-adaptive PCPs, e.g.
$$P = PCP_{1, \frac{5}{8} + \epsilon}(log(n), 3)$$
and they construct an adaptive PCP finally showing that $NP = PCP_{1, \frac{1}{2}+\epsilon}(log (n), 3)$.</p>

<p>Then again the definition in the textbook from Arora, Barak (and in other lectures) uses explicitly non-adaptive verifiers with perfect completeness (well, with soundness $\frac{1}{2}$). </p>

<p>Could someone give further explanations on this? Are different definitions with soundness paramter $\frac{1}{2}$ equivalent?</p>

<p>And one further question: Is it possible to construct a linear dictatorship test (as basis of the Hastad Verifier) which is complete AND non-adaptive?</p>

CC BY-SA 3.0
2014-11-01T21:10:38.500Z
Does the Arora-Barak definition you refer to use 3 queries, or a larger constant?
Or Meir
CC BY-SA 3.0
2014-11-01T21:17:42.867Z
The Hastad verifier in the book makes exactly 3 queries, is non-adaptive and has no full completeness. But with "definition" I meant the general definition of PCP verifiers, not specifically the Hastad verifier.
SpaceMonkey
<adaptive>
Adaptive vs. non-adaptive PCP verifiers
SpaceMonkey
# Adaptive vs. non-adaptive PCP verifiers

(Asked by: username_0 on 2014-11-01)

I'm looking through some lectures and books to understand the PCP verifier constructed by Hastad. I noticed that the subtle difference of an adaptive or non-adaptive PCP verifier seems to correspond to verifier with perfect or non-perfect completeness.

In "A tight characterization of NP with 3 query PCPs" the authors point out that there are (due to Trevisan and Zwick) strong restrictions using non-adaptive PCPs, e.g.
$$P = PCP\_{1, \frac{5}{8} + \epsilon}(log(n), 3)$$
and they construct an adaptive PCP finally showing that $NP = PCP\_{1, \frac{1}{2}+\epsilon}(log (n), 3)$.

Then again the definition in the textbook from Arora, Barak (and in other lectures) uses explicitly non-adaptive verifiers with perfect completeness (well, with soundness $\frac{1}{2}$).

Could someone give further explanations on this? Are different definitions with soundness paramter $\frac{1}{2}$ equivalent?

And one further question: Is it possible to construct a linear dictatorship test (as basis of the Hastad Verifier) which is complete AND non-adaptive?

**Tags:** adaptive

> **Comments:**
> **username_1**: Does the Arora-Barak definition you refer to use 3 queries, or a larger constant?  
> **username_0**: The Hastad verifier in the book makes exactly 3 queries, is non-adaptive and has no full completeness. But with "definition" I meant the general definition of PCP verifiers, not specifically the Hastad verifier.  

---

## 0 answers

