Two-query PCPs and binary constraint graphs

For the graph-to-verifier direction, order the $m$ edges and use $r_G=\lceil {\log }_{2}m\rceil$ random bits to choose one of $2^{r_G}$ indices. For indices below $m$, query the edge's endpoints in its specified order and accept exactly when their labels satisfy its relation; surplus indices accept without queries. This is nonadaptive, and a loop reads the same proof symbol twice. For a fixed labeling $\sigma$, exactly $m{\mathrm{UNSAT}}_{\sigma }(G)$ of the $m$ real-edge indices reject, so the rejection probability is $m{\mathrm{UNSAT}}_{\sigma }(G)\mathrm{/}{2}^{r_G}$. Since $2^{r_G}<2m$, this is at least half the labeling's unsatisfaction; taking the minimum over labelings gives the stated graph-unsatisfiability bound.

For the verifier-to-graph direction, enumerate its $2^r$ random tapes. On each tape the nonadaptive query addresses are fixed. Make one ordered edge per tape with endpoint vertices equal to the two queried proof positions, and put in its relation exactly the answer pairs on which that tape accepts. If the two addresses coincide, make a loop with relation $\{(a,a):V\text{ accepts on this tape when the repeated location returns }a\}$; its off-diagonal entries are empty. If there is one query, use a fresh dummy vertex as the second endpoint and let the relation ignore its label; if there are no queries, use a loop at a dummy vertex with relation ${\mathrm{\Sigma }}^2$ when that tape accepts and the empty relation when it rejects. Retain parallel edges, including identical tape outcomes, so the graph has exactly $2^r$ edges.

For any fixed proof $\pi$, label each retained proof-position vertex by its symbol and each dummy by a fixed default symbol in the nonempty alphabet. The edge for a tape is satisfied exactly when that run accepts, so its satisfied-edge fraction equals $\mathrm{Pr}[V^{\pi }(x)\text{ accepts}]$. Conversely, any graph labeling extends to a proof by assigning its symbols at retained positions and a fixed default symbol at every unused proof position; hence maximizing over proofs gives exactly $\mathrm{val}(G_{V,x})$. Since the proof space is finite, this maximum is attained.

At most two proof positions occur on each of $2^r$ tapes, so after removing unused proof positions the graph has at most $2^{r+1}+1$ vertices, and its fixed-size relation tables and endpoint names can be written in polynomial time in $\mathrm{\mid }x\mathrm{\mid }+2^r$. Thus $r=O(\log \mathrm{\mid }x\mathrm{\mid })$ gives a polynomial-size graph. The exact value equality in step 2.1, [F3] and [F4] transfer both threshold directions: value at least $c$ iff some fixed proof accepts with probability at least $c$, and value at most $s$ iff every fixed proof accepts with probability at most $s$. For binary proofs, choose $k=\max (1,\lceil {\log }_2\mathrm{\mid }\mathrm{\Sigma }\mathrm{\mid }\rceil )$ and a fixed surjection $D:\{0,1{\}}^k\to \mathrm{\Sigma }$; decoding each queried block makes every bit proof a $\mathrm{\Sigma }$-symbol proof, and every symbol proof has a block encoding, so the maximum is unchanged while at most $2k=O(1)$ bits are queried.