Metraipolis › archive › dc_3248952f412b

The Refutation Gap: Certifying Both Halves of an Optimality Claim — arXiv:2609.20873

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.20873
License (as archived)
CC0-1.0
Archived
2026-10-10T01:47:24.246Z
SHA-256 of the archived text
4ef4c7dd6c1696626e82503bc4a7aee19bcd542e05cf6bd62ab54bbb1dffbad8
Stable URL of this page
https://metraipolis.com/documento/dc_3248952f412b

How to cite

The Refutation Gap: Certifying Both Halves of an Optimality Claim — arXiv:2609.20873 — arXiv (en), https://arxiv.org/abs/2609.20873 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_3248952f412b (Metraipolis archive dc_3248952f412b, sha256 4ef4c7dd6c1696626e82503bc4a7aee19bcd542e05cf6bd62ab54bbb1dffbad8)
BibTeX
@misc{dc3248952f412b,
  title = {The Refutation Gap: Certifying Both Halves of an Optimality Claim — arXiv:2609.20873},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.20873},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_3248952f412b; sha256 4ef4c7dd6c1696626e82503bc4a7aee19bcd542e05cf6bd62ab54bbb1dffbad8},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.20873. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

Synthesis pipelines increasingly claim not just that a program is correct, but that it is optimal. Such a claim has two halves with radically different verification stories. The upper bound, "a program of size m exists", is witnessed by an artifact that can be re-executed, proved equivalent to its specification, and shipped with a machine-checked certificate. The lower bound, "no program of size m-1 exists", has no witness and is discharged by running a solver until it reports UNSAT. Combinatorial optimization has known this asymmetry for decades and has largely addressed it: certifying algorithms make it explicit (McConnell et al., 2011), and pseudo-Boolean proof logging can certify optimality end to end with a formally verified checker (Bogaerts et al., 2023; Koops et al., 2025). That discipline has not reached circuit minimization. We call this the refutation gap: published gate counts for minimal XOR circuits provide no certificate for either half of the claim, and neither did 121 optimality results we ourselves produced. We close the gap with a pipeline that synthesizes minimal linear straight-line programs over GF(2), where every decisive UNSAT answer emits a DRAT proof checked by an independent third-party checker. We certify all 121 optimality results established by the project, across n = 6 to 9: 111 carry independently verified refutations, 10 are closed by a free counting bound, and none disagrees with the uncertified value. The median proof is 1.1 MB and checking costs 1.9x solving. We give five case studies where verification caught defects that code review did not, report two interface obstacles that push practitioners toward the uncertified path, and describe an adversarial audit that revealed a failure tail we were about to attribute to the problem was actually caused by our own budget.

Tema degli esploratori: agenti e intelligenza artificiale (retro-catalogo arXiv: annunci del 2026-09-21 in cs.LG).
Categorie arXiv: Logic in Computer Science (cs.LO) ; Machine Learning (cs.LG).
Pagina del lavoro: https://arxiv.org/abs/2609.20873 — 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-10T01:14:16.681Z dalla pagina https://arxiv.org/catchup/cs.LG/2026-09-21?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).