Contextual Fraction Beyond Satisfiability: Pure NAE Completeness, Exact Orbit Packings, and Width Barriers

Abstract

The contextual fraction measures how much globally consistent probability can be packed beneath prescribed local event probabilities. We study the quantitative regime in which supported global assignments exist but the contextual fraction is nontrivial. For balanced relational lifts, we identify the noncontextual fraction with a capacity-constrained packing of global homomorphisms and prove an exact orbit-capacity quotient under finite group symmetries. For the uniform Boolean relation $\NAE_3$, this becomes a minority-position congestion game on proper hypergraph two-colourings: \[ \NCF(e_H)=\frac{1}{3β(H)}. \] We also obtain a minimax dual, a cut-polytope formulation, and explicit values $2/3$ and $1/2$. For exact hardness, we map a graph $G$ to an always-two-colourable anchor hypergraph $A(G)$ with \[ \NCF(e_{A(G)})=1 \Longleftrightarrow χ_f(G)\le3. \] We prove quantitative stability in terms of ${\chi }_f(G)$ and construct a six-edge pure-$\NAE_3$ equality gadget that preserves the full noncontextual fraction under bounded-occurrence compilation. Thus deciding $\CF=0$ is NP-complete for simple $3$-uniform hypergraphs of maximum degree seven, even with a supplied proper two-colouring. We further prove \[ \NCF(\widehat e^{\,\vartheta}) =\vartheta+(1-\vartheta)\NCF(e). \] This yields NP-hardness of distinguishing $\NCF=1/2$ from $\NCF\ge2/3$ on an always-satisfiable fixed five-ary switch template, and additive hardness below $1/12$. A gated colouring construction gives hardness within $1/2-\epsilon$ for every $\epsilon >0$. Finally, bounded-treewidth instances admit exact compact extended formulations, while explicit families have extension complexity $2^{\Omega (\sqrt{N})}$ via cut-polytope projections.

arXiv comment20 pages, 3 Tables, 0 Figures