A constant-query PCP verifier yields constant-gap Max-3SAT

Fix $L\in NP$ and an input $x$ of length $n$. Under the Axiom of Choice hypothesis of [F6], [F1] supplies a verifier $V$ for $L$ with perfect completeness $c=1$, fixed soundness $s_0<1$, a bound $r(n)=O(\log n)$, a constant query bound $q$, and a fixed polynomial bound $p$ on the addressable proof length. By [F7], fix a rational $s$ with $s_0<s<1$; the verifier also has soundness at most $s$. This rational constant may be hardcoded without computing $s_0$. Put $R:=2^{r(n)}$, so $R\ge 1$ and $R$ is polynomially bounded in $n$.

For each coin string $\sigma$, the nonadaptive verifier queries a set $Q_{\sigma }$ of distinct proof locations determined by $x$ and $\sigma$, with $\mathrm{\mid }{Q}_{\sigma }\mathrm{\mid }\le q$; let $P_{\sigma }\subseteq \{0,1{\}}^{Q_{\sigma }}$ be the finite set of local assignments on which $V$ rejects, $\mathrm{\mid }{P}_{\sigma }\mathrm{\mid }\le 2^q$. If $Q_{\sigma }=\mathrm{\varnothing }$, then $P_{\sigma }$ is either empty (the verifier accepts) or the single empty assignment (the verifier rejects).

Build a CNF formula ${\mathrm{\Phi }}_x$ over one Boolean variable per addressable proof location, treating each coin string $\sigma$ in exactly one of three cases. If $P_{\sigma }=\mathrm{\varnothing }$, insert one tautology $w\vee \mathrm{\neg }w\vee w$ on a fresh bit reserved to $\sigma$. If $Q_{\sigma }=\mathrm{\varnothing }$ and the verifier rejects, insert only the contradictory pair $z\vee z\vee z$ and $\mathrm{\neg }z\vee \mathrm{\neg }z\vee \mathrm{\neg }z$ on a fresh bit reserved to $\sigma$; do not insert an empty clause. Otherwise $Q_{\sigma }\mathrm{\ne }\mathrm{\varnothing }$: for every $\rho \in P_{\sigma }$ insert $C_{\sigma ,\rho }={\bigvee }_{i\in Q_{\sigma }}{\mathrm{\ell }}_i(\rho )$, where ${\mathrm{\ell }}_i(\rho )$ is $\mathrm{\neg }{\pi }_i$ if $\rho (i)=1$ and ${\pi }_i$ if $\rho (i)=0$. This clause is falsified exactly by the assignments realizing $\rho$. Every inserted clause has width between $1$ and $\max (q,3)$, and the construction is an explicit finite procedure.

Convert each clause of width $d$ into a block of 3-clauses with fresh auxiliary bits reserved to that block: for $d=3$ keep the clause; for $d=2$ write ${\mathrm{\ell }}_1\vee {\mathrm{\ell }}_2\vee {\mathrm{\ell }}_2$; for $d=1$ write ${\mathrm{\ell }}_1\vee {\mathrm{\ell }}_1\vee {\mathrm{\ell }}_1$; for $d\ge 4$ use fresh bits $y_1,\dots ,y_{d-3}$ and the chain ${\mathrm{\ell }}_1\vee {\mathrm{\ell }}_2\vee y_1$, then $\mathrm{\neg }{y}_k\vee {\mathrm{\ell }}_{k+2}\vee y_{k+1}$ for $1\le k\le d-4$, then $\mathrm{\neg }{y}_{d-3}\vee {\mathrm{\ell }}_{d-1}\vee {\mathrm{\ell }}_d$; each written clause has exactly three literal occurrences, so $F_x$ is a 3-CNF in the format of [F4], and distinct blocks share no auxiliary bit.

For $1\le d\le 3$, padding or keeping a clause preserves its truth value. For $d\ge 4$, if all original literals are false, satisfying the first clause would force $y_1$ true, the intermediate clauses would force all subsequent $y_i$ true, and the last clause would then be false; thus every auxiliary assignment falsifies at least one clause. Conversely, if ${\mathrm{\ell }}_k$ is true, assigning $y_i$ true for $i\le k-2$ and false for $i\ge k-1$ satisfies the whole chain. The tautology of step 2.1 is always satisfied, while its contradictory pair always has exactly one falsified clause.

Count clause occurrences in the blocks checked in step 4.1. Each coin string contributes at least one: the always-accepting case contributes one tautology, the no-query rejecting case contributes two clauses, and every other case contributes between $1$ and $2^q$ pattern blocks, each of at most $\max (1,q-2)$ clauses. Thus $K:=(2^q+1)\max (2,q-2)$ bounds the contribution of any coin string, including $q=0$, and $R\le M\le KR$. In particular $M\ge 1$ and is the scale of [F5].

Suppose $x\in L$. By perfect completeness some fixed proof $\pi$ is accepted on every one of the $R$ coin strings, so for no $\sigma$ does the realized local pattern lie in $P_{\sigma }$; every clause $C_{\sigma ,\rho }$ is therefore satisfied by the proof variables, the tautology clauses are satisfied by their fresh bits, and step 4.1 supplies auxiliary values satisfying all 3-clauses of every block. Hence all $M$ clauses can be satisfied simultaneously and ${\mathrm{OPT}}_{\mathrm{M}\mathrm{a}\mathrm{x}3\mathrm{S}\mathrm{A}\mathrm{T}}(F_x)=M$.

Suppose $x\mathrm{\notin }L$ and fix any assignment to all variables of $F_x$. By soundness at least $(1-s)R$ coin strings reject its fixed proof part. For each such $\sigma$ with $Q_{\sigma }\mathrm{\ne }\mathrm{\varnothing }$, the realized rejected pattern falsifies $C_{\sigma ,\rho }$, so step 4.1 forces a falsified 3-clause in its block. For a rejecting $\sigma$ with $Q_{\sigma }=\mathrm{\varnothing }$, its contradictory pair has a falsified clause instead. Distinct coin strings contribute distinct clause occurrences, even when the written clauses coincide, so at least $(1-s)R$ occurrences are falsified. Hence ${\mathrm{OPT}}_{\mathrm{M}\mathrm{a}\mathrm{x}3\mathrm{S}\mathrm{A}\mathrm{T}}(F_x)\le M-(1-s)R$.

Set $\delta :=(1-s)\mathrm{/}K>0$, a fixed rational constant because $s<1$ is rational and $K$ is a positive integer. From $M\le KR$ we get $R\ge M\mathrm{/}K$, so step 6.2 gives ${\mathrm{OPT}}_{\mathrm{M}\mathrm{a}\mathrm{x}3\mathrm{S}\mathrm{A}\mathrm{T}}(F_x)\le M-(1-s)R\le M-(1-s)M\mathrm{/}K=(1-\delta )M$.

The map $x\mapsto F_x$ is deterministic and polynomial-time: the verifier is a uniform polynomial-time algorithm, $R=2^{O(\log n)}$ is polynomially bounded, each coin string's queries and local predicate are computed in polynomial time, and polynomially many clauses of constant width are written; $M\ge 1$ by step 5.1. Therefore $x\in L$ implies ${\mathrm{OPT}}_{\mathrm{M}\mathrm{a}\mathrm{x}3\mathrm{S}\mathrm{A}\mathrm{T}}(F_x)=M$ and $x\mathrm{\notin }L$ implies ${\mathrm{OPT}}_{\mathrm{M}\mathrm{a}\mathrm{x}3\mathrm{S}\mathrm{A}\mathrm{T}}(F_x)\le (1-\delta )M$ with the fixed $\delta >0$ of step 7.1; by [F5] these are the yes-side equality and no-side value inequality of the constant-gap Max-3SAT statement with scale $M$.