PCP verifier resources and deterministic proof strings

Fix a finite proof alphabet $\mathrm{\Gamma }$ independent of the input length. A nonadaptive PCP verifier with resource bounds $r,q,L$ is a uniform polynomial-time randomized oracle algorithm $V$ such that, on each input $x\in \{0,1{\}}^n$, it uses at most $r(n)$ unbiased random bits, reads a fixed proof $\pi \in {\mathrm{\Gamma }}^{L(n)}$ at at most $q(n)$ locations, and outputs accept or reject. For every input and every coin string, the queried locations are computed from $x$ and the coins before any proof symbol is read; each lies in $[L(n)]$. Repeated locations count as repeated queries. The bound $L(n)$ is polynomial in $n$ and counts addressable symbols, not the bits in their binary addresses. When $L(n)=0$, the proof is empty and the verifier makes no queries.

For a fixed input $x$ and a fixed proof $\pi$, the acceptance probability is the proportion of the $2^{r(n)}$ coin strings on which $V^{\pi }(x)$ accepts. The coin set is nonempty even when $r(n)=0$, in which case it contains the empty string. Completeness asks for one fixed proof on each yes input; soundness bounds the acceptance probability for every fixed proof on each no input. Thus the proof is not resampled when the verifier runs. This oracle version refines the verifier viewpoint of The class NP via polynomial-time verifiers, with its coin space interpreted as the uniform finite probability space of The uniform probability space on a nonempty finite set.