| _version_ | 1866901070971666432 |
|---|---|
| author | Figurelli, Rogério |
| author_facet | Figurelli, Rogério |
| contents | <p>Hard problems fail in two predictable ways: we overfit to tractable corners, or we accept persuasive narratives that cannot be replayed. Our work proposes a receipt-first, replay-first program for P vs NP in which the unit of progress is a subfield: a regime-bounded slice of the problem with locked scope, admissible transforms, invariants, falsifiers, and a solver proofpack. Progress becomes promotable only when accompanied by verifiable witnesses and append-only receipts that support clean-room replay. We formalize a universal budgeted hypothesis (UCCB(k)) that, if satisfied under a locked witness menu, yields a polynomial-time decision route for SAT. We then show why expander-coupled families stress this hypothesis by collapsing separator- and treewidth-style witnesses and by forcing frontier growth that breaks locally verified elimination-style compilation traces. Finally, we map the frontier cleanly: proof-carrying decisions (W6′) re-express the core question as universal polynomial certificate generation, while DRIFT-style proofpacks can provide honest intermediate deliverables (e.g., SAT ∈ BPP) without overclaiming P = NP. The result is a Clay-compatible research loop: it produces publishable negative tracks and transparent conditional frontiers, and it prevents illusory “near-proofs” via explicit stop rules.</p> |
| format | Recurso digital |
| id | zenodo_https___doi_org_10_5281_zenodo_18842736 |
| institution | Zenodo |
| language | |
| publishDate | 2026 |
| publisher | Zenodo |
| record_format | zenodo |
| spellingShingle | Subfields as the Unit of Progress: A Modular Path Through P vs NP Figurelli, Rogério P vs NP SAT NP-completeness proofpacks subfields receipts <p>Hard problems fail in two predictable ways: we overfit to tractable corners, or we accept persuasive narratives that cannot be replayed. Our work proposes a receipt-first, replay-first program for P vs NP in which the unit of progress is a subfield: a regime-bounded slice of the problem with locked scope, admissible transforms, invariants, falsifiers, and a solver proofpack. Progress becomes promotable only when accompanied by verifiable witnesses and append-only receipts that support clean-room replay. We formalize a universal budgeted hypothesis (UCCB(k)) that, if satisfied under a locked witness menu, yields a polynomial-time decision route for SAT. We then show why expander-coupled families stress this hypothesis by collapsing separator- and treewidth-style witnesses and by forcing frontier growth that breaks locally verified elimination-style compilation traces. Finally, we map the frontier cleanly: proof-carrying decisions (W6′) re-express the core question as universal polynomial certificate generation, while DRIFT-style proofpacks can provide honest intermediate deliverables (e.g., SAT ∈ BPP) without overclaiming P = NP. The result is a Clay-compatible research loop: it produces publishable negative tracks and transparent conditional frontiers, and it prevents illusory “near-proofs” via explicit stop rules.</p> |
| title | Subfields as the Unit of Progress: A Modular Path Through P vs NP |
| topic | P vs NP SAT NP-completeness proofpacks subfields receipts |
| url | https://doi.org/10.5281/zenodo.18842736 |