Metraipolis › archive › dc_08d2bc193e4c
Contextual Fraction Beyond Satisfiability: Pure NAE Completeness, Exact Orbit Packings, and Width Barriers — arXiv:2609.20281
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.20281
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-10T05:45:26.520Z
- SHA-256 of the archived text
f94fd2e1d0f925a86e22ad36f72160c4d689d4030bccdb34f22ea33665ddcaa5- Stable URL of this page
https://metraipolis.com/documento/dc_08d2bc193e4c
How to cite
Contextual Fraction Beyond Satisfiability: Pure NAE Completeness, Exact Orbit Packings, and Width Barriers — arXiv:2609.20281 — arXiv (en), https://arxiv.org/abs/2609.20281 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_08d2bc193e4c (Metraipolis archive dc_08d2bc193e4c, sha256 f94fd2e1d0f925a86e22ad36f72160c4d689d4030bccdb34f22ea33665ddcaa5)
BibTeX
@misc{dc08d2bc193e4c,
title = {Contextual Fraction Beyond Satisfiability: Pure NAE Completeness, Exact Orbit Packings, and Width Barriers — arXiv:2609.20281},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.20281},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_08d2bc193e4c; sha256 f94fd2e1d0f925a86e22ad36f72160c4d689d4030bccdb34f22ea33665ddcaa5},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.20281. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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\beta(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 \chi_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-\varepsilon$ for every $\varepsilon>0$. Finally, bounded-treewidth instances admit exact compact extended formulations, while explicit families have extension complexity $2^{\Omega(\sqrt N)}$ via cut-polytope projections.
Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-18 in cs.CC).
Categorie arXiv: Computational Complexity (cs.CC) ; Discrete Mathematics (cs.DM).
Pagina del lavoro: https://arxiv.org/abs/2609.20281 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-10T05:12:38.404Z dalla pagina https://arxiv.org/catchup/cs.CC/2026-09-18?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).