Constant-gap binary CSP is NP-hard

Under [A1], use the current Dinur-transformation suppliers [F3]–[F6], [F10] and [F11], whose proof route uses Choice through expander spectral theory and algebraic embedding extension. By [F2] and [F8] there is a deterministic polynomial-time total reduction $g$ from $L$ to 3-SAT, which we fix; put $\phi :=g(x)$, with $m$ clauses, each of exactly three literal occurrences. By [F1] the formula $\phi$ has a polynomial-time computable graph $G_{\phi }$ over $\widehat{\mathrm{\Sigma }}=\{B(0),B(1)\}\bigsqcup \{T(a):a\in \{0,1{\}}^3\}$ with exactly $3m$ edges, and by [F10] the transformation alphabet is ${\mathrm{\Sigma }}_{\star }=\{B(0),B(1)\}\bigsqcup \{0,1{\}}^6$. Let $f$ be the fixed injection $f:\widehat{\mathrm{\Sigma }}\to {\mathrm{\Sigma }}_{\star }$ with $f(B(i))=B(i)$ and $f(T(a))=(a,0,0,0)$, and let $\widehat{G}$ be the graph with the same vertices, incidence slots and endpoint orders as $G_{\phi }$ and relations $f(R_e)=\{(f(a),f(b)):(a,b)\in R_e\}$; then $\widehat{G}$ is an explicit binary constraint graph over ${\mathrm{\Sigma }}_{\star }$ with exactly $3m$ edges. Put $K:=\lceil {\log }_2(3m)\rceil$ if $m\ge 1$, and define $h(\phi ):=T^K(\widehat{G})$ for $m\ge 1$ (a finite ${\mathrm{\Sigma }}_{\star }$-graph by [F6]) while $h(\phi )$ is the edgeless graph over ${\mathrm{\Sigma }}_{\star }$ for $m=0$.

For a labeling $\sigma$ of $\widehat{G}$, define ${\sigma }_0(v):=f^{-1}(\sigma (v))$ if $\sigma (v)\in f(\widehat{\mathrm{\Sigma }})$ and ${\sigma }_0(v):=B(0)$ otherwise. If an edge $e$ is satisfied by $\sigma$ in $\widehat{G}$, then $(\sigma (u),\sigma (v))\in f(R_e)$, so both labels lie in $f(\widehat{\mathrm{\Sigma }})$ and $({\sigma }_0(u),{\sigma }_0(v))=(f^{-1}\sigma (u),f^{-1}\sigma (v))\in R_e$: the same edge is satisfied by ${\sigma }_0$ in $G_{\phi }$. Hence ${\mathrm{val}}_{\sigma }(\widehat{G})\le {\mathrm{val}}_{{\sigma }_0}(G_{\phi })\le \mathrm{val}(G_{\phi })$ for every $\sigma$ by [F9], so $\mathrm{val}(\widehat{G})\le \mathrm{val}(G_{\phi })$; conversely the labelings $f\circ \tau$ of $\widehat{G}$ for $\tau :V\to \widehat{\mathrm{\Sigma }}$ realize the same satisfied edges, so $\mathrm{val}(\widehat{G})\ge \mathrm{val}(G_{\phi })$. Thus $\mathrm{val}(\widehat{G})=\mathrm{val}(G_{\phi })$ and $\mathrm{UNSAT}(\widehat{G})=\mathrm{UNSAT}(G_{\phi })$.

For the size and time bound, each iterate multiplies the number of edge records by at most $C_E$ and has at most $C_V$ times the previous number of edge records vertices by [F11], so after $i\le K=O(\log m)$ rounds $\mid E(T^i(\widehat{G}))\mid \le C_E^i\cdot 3m$ and, for $i\ge 1$, $\mid V(T^i(\widehat{G}))\mid \le C_V\mid E(T^{i-1}(\widehat{G}))\mid \le C_V{C}_E^{i-1}\cdot 3m$, both of size $m^{O(1)}$. Each of the $K+1$ applications of $T$ runs in deterministic polynomial time in the bit length of its input by [F11], and that input has size $m^{O(1)}$ throughout, so the computation of $h(\phi )$ from $\phi$ is deterministic polynomial time; the relabeling $G_{\phi }\mapsto \widehat{G}$ and the reduction $g$ are also polynomial time.

Suppose $x\in L$, so $\phi \in 3$-SAT. If $m=0$, then $h(\phi )$ is edgeless, so $\mathrm{val}(h(\phi ))=1$ by [F9]. If $m\ge 1$, then $\mathrm{val}(G_{\phi })=1$ by [F1], hence $\mathrm{val}(\widehat{G})=1$ by step 2.1, and the zero-unsatisfaction clause [F4] of the iteration lemma applied to $G_0=\widehat{G}$ with $\mid E(\widehat{G})\mid =3m$ gives $\mathrm{UNSAT}(h(\phi ))=0$, that is, $\mathrm{val}(h(\phi ))=1$. In both cases $\mathrm{val}(h(\phi ))\ge 1$.

Suppose $x\mathrm{\notin }L$, so $\phi \mathrm{\notin }3$-SAT is unsatisfiable; a formula with no clauses is satisfiable, so $m\ge 1$. By [F1], $\mathrm{UNSAT}(G_{\phi })\ge 1\mathrm{/}(3m)>0$ and $\mid E(G_{\phi })\mid =3m\ge 1$, and step 2.1 transfers both to $\widehat{G}$, whose edge count is $3m$. The positive-gap clause [F3] of the iteration lemma applied to $G_0=\widehat{G}$ with $\mid E(\widehat{G})\mid =3m$ and $K=\lceil {\log }_2(3m)\rceil$ gives $\mathrm{UNSAT}(h(\phi ))\ge \alpha$, hence $\mathrm{val}(h(\phi ))\le 1-\alpha$ by [F9].

The map $f_L:x\mapsto h(g(x))$ is total, deterministic and polynomial time by steps 1.1 and 2.2, and it sends instances of $L$ to graphs of value at least $1$ by step 3.1 and instances outside $L$ to graphs of value at most $1-\alpha$ by step 3.2. By [F7] the target pair is $\mathrm{GapCSP}(1,1-\alpha )$ with $c=1$ and $s=1-\alpha$, and by [F8] this is a deterministic polynomial-time many-one promise reduction in the two-sided sense. Since $L\in \mathrm{N}\mathrm{P}$ was arbitrary, $\mathrm{GapCSP}(1,1-\alpha )$ is NP-hard.