Fixed-alphabet reduction with constant gap retention

Define $A_{\mathrm{\Sigma }}(G)$ to be the binary graph produced by applying Bounded-arity Boolean constraints become binary graph constraints with $q=6$ to the Boolean system $H=G\circ P$ when $E(G)\mathrm{\ne }\mathrm{\varnothing }$, and to the empty system when $E(G)=\mathrm{\varnothing }$. Its output alphabet is the $\widehat{\mathrm{\Sigma }}$ displayed in the statement, independent of $\mathrm{\Sigma }$: the two bit labels $B(0),B(1)$ and the $64$ tuple labels $T(a)$, $a\in \{0,1{\}}^6$.

Suppose first that $E(G)=\mathrm{\varnothing }$. Then $H$ has no variables and no constraints by [F1], so $\mathrm{val}(H)=1$ and $\mathrm{UNSAT}(H)=0$ by [F8]; the conversion of the empty system is an edgeless graph, so $\mathrm{val}(A_{\mathrm{\Sigma }}(G))=1$ and $\mathrm{UNSAT}(A_{\mathrm{\Sigma }}(G))=0$ by [F8] and [F7]. The input also has $\mathrm{val}(G)=1$ and $\mathrm{UNSAT}(G)=0$, and $0\le C_{\mathrm{\Sigma }}\cdot 0$ holds for every constant. This disposes of the edgeless case for all four clauses.

Suppose now that $E(G)\mathrm{\ne }\mathrm{\varnothing }$. By [F3] and [F4], for a fixed $\mathrm{\Sigma }$ every edge circuit has at most $N_{\mathrm{\Sigma }}:=2\mathrm{\ell }+O(W^3)$ wires, with the implicit constant of [F3] depending only on $\mathrm{\Sigma }$; hence every local gadget size satisfies $q_e\le Q_{\mathrm{\Sigma }}:=2^{7N_{\mathrm{\Sigma }}^2+4}$. The least common multiple $M$ of the finitely many numbers $q_e$ therefore divides $\mathrm{lcm}(1,\dots ,Q_{\mathrm{\Sigma }})=:M_{\mathrm{\Sigma }}$, a finite integer depending only on $\mathrm{\Sigma }$. Thus $H$ has $Mm\le M_{\mathrm{\Sigma }}m$ constraints by [F1], each of arity at most six, and its variable set is the union of the $2\mathrm{\ell }$ coordinates of each active block and the $m$ edge-private auxiliary lists. For the explicit vertex count, [F10] shows that each local gadget has at most $q_e$ variables, so the number of edge-private variables contributed by one edge is at most $q_e\le q_{\max }:={\max }_e{q}_e\le Q_{\mathrm{\Sigma }}$.

Assume $\mathrm{val}(G)=1$. Then [F5] gives $\mathrm{val}(H)=1$, so $H$ has a labeling satisfying every one of its constraints. Applying the perfect-completeness clause of [F7] to that labeling produces a labeling of $A_{\mathrm{\Sigma }}(G)$ satisfying every output edge, so $\mathrm{val}(A_{\mathrm{\Sigma }}(G))=1$.

Assume $E(G)\mathrm{\ne }\mathrm{\varnothing }$ and apply the gap clause of [F7] to $H$ with $q=6$. Combined with [F6] and the code distance $\delta =1\mathrm{/}2$ of [F2], the transfer factor ${\rho }_0\delta \mathrm{/}4=1\mathrm{/}8000$ gives $\mathrm{UNSAT}(A_{\mathrm{\Sigma }}(G))\ge \frac{\mathrm{UNSAT}(H)}{6}\ge \frac{1}{6\cdot 8000}\mathrm{UNSAT}(G)=\frac{1}{48000}\mathrm{UNSAT}(G)=\kappa \mathrm{UNSAT}(G)\mathrm{.}$

Conversely assume $\mathrm{val}(A_{\mathrm{\Sigma }}(G))=1$. Then $\mathrm{UNSAT}(A_{\mathrm{\Sigma }}(G))=0$ by [F8]. If $E(G)=\mathrm{\varnothing }$ then $\mathrm{val}(G)=1$ by [F8]. If $E(G)\mathrm{\ne }\mathrm{\varnothing }$, then step 1.5 gives $\kappa \mathrm{UNSAT}(G)\le 0$, so $\mathrm{UNSAT}(G)=0$ and $\mathrm{val}(G)=1$. This proves the reverse direction of clause 1, and step 1.4 proves the forward direction.

For the size clause assume $E(G)\mathrm{\ne }\mathrm{\varnothing }$. The conversion adds at most six edge records per constraint of $H$ by [F7], so $\mid E(A_{\mathrm{\Sigma }}(G))\mid \le 6\mid E(H)\mid =6Mm\le 6M_{\mathrm{\Sigma }}m,$ using step 1.3. Its vertex set consists of the vertices of $H$, one per variable, together with one private tuple vertex per constraint of $H$; by [F1] the number of vertices of $H$ is at most $(2\mathrm{\ell }+q_{\max })m$, where $2\mathrm{\ell }$ accounts for a block per nonisolated vertex (at most two per edge), and [F10] together with step 1.3 bounds the private variables of each edge gadget by $q_{\max }$. Hence $\mid V(A_{\mathrm{\Sigma }}(G))\mid \le (2\mathrm{\ell }+q_{\max }+M_{\mathrm{\Sigma }})m$ by [F1] and [F9]. Both bounds hold with $C_{\mathrm{\Sigma }}:=6M_{\mathrm{\Sigma }}+2\mathrm{\ell }+Q_{\mathrm{\Sigma }}+M_{\mathrm{\Sigma }}$, a constant depending only on $\mathrm{\Sigma }$; for $E(G)=\mathrm{\varnothing }$ the output is edgeless and both quantities are zero.

The map $A_{\mathrm{\Sigma }}$ is deterministic: the robust edge circuits and the two-piece tester are deterministic constructions, the least common multiple and the conversion are computed from finite explicit lists, and no sampling or selection from an infinite family occurs. For fixed $\mathrm{\Sigma }$ each edge contributes a search over a constant-size tester transcript enumeration and a constant number of copied constraints, so all relation tables and endpoint names are written in time polynomial in the input encoding length plus the output bit length $O_{\mathrm{\Sigma }}(m\log (m+2))$, which is itself polynomial in the input length by clause 2.

Clauses 1, 2, 3 and 4 are now proved: clause 1 by steps 1.4 and 2.1, clause 2 by step 2.2, clause 3 by step 1.5 together with the trivial edgeless identity of step 1.2, and clause 4 by step 3.1. The defining constant is $\kappa ={\rho }_0\delta \mathrm{/}(4\cdot 6)=(1\mathrm{/}1000)(1\mathrm{/}2)\mathrm{/}24=1\mathrm{/}48000$, and the output alphabet is $\widehat{\mathrm{\Sigma }}$ of size $2+2^6=66$ for every $\mathrm{\Sigma }$.