SOURCE-LINKED INTELLIGENCE

The Refutation Gap: Certifying Both Halves of an Optimality Claim

arXiv · AI, language, vision and robotics · article · Sep 16, 2026 · UTC

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 algori

Read original source ↗ Open in workspace

recordType

paper

region

Global