Research · Papers · Exact answers in open problems · ML-095
Open status and catalogue corrections for resolution hardness h_11
h_11 ≥ 28 remains undetermined; reproduced h_8 = 19, h_9 = 22; candidate census corrected to 626,973 with missing RSMU(8,10) identified
Published 2026-09-06
For everyone
Plain summary
Resolution hardness measures the shortest mathematical proof that a logic formula has no solution, grouped by formula size m. We still don't know the exact value for h_11. Earlier work showed h_11 is at least 28 and pinned down smaller cases like h_10 = 26.
We independently verified h_8 = 19 and h_9 = 22. Checking h_10 or solving h_11 hit hard compute limits. We also found two record-keeping errors in published research: the public Zenodo candidate catalogue drops the entire RSMU(8,10) folder, and the candidate count needed to test whether hardness reaches 29 was misreported. The real candidate count is 626,973. Finding h_11 remains open.
Result
The exact resolution hardness h_11 remains open above the lower bound h_11 ≥ 28. Independent verification reproduced h_8 = 19 and h_9 = 22.
The singular candidate census for formulas that could attain hardness 29 is corrected to 626,973. The published Zenodo archive omits the RSMU(8,10) directory.
Setting and definitions
Let h_m denote the maximum resolution hardness (minimal proof size for unsatisfiable CNF formulas) over formulas of size m in the standard minimal unsatisfiable classification. RSMU(n, m) designates regular singular minimally unsatisfiable candidate formula sets on n variables with m clauses. A singular candidate set consists of formula extensions evaluated against base structures across the 73,517 known base formulas.
Method
Computations were executed in box frontier/h11/ and logged in lanes/hardness-h11/VERIFY.md and WALL.md.
The shortest-proof incremental solving loop ran with an independent proof checker for lower m values, reproducing h_8 = 19 and h_9 = 22. For h_10 = 26, the run timed out under the allocable compute budget: 3.5 minutes at size s = 22, 13 minutes at s = 23, and over 40 minutes at s = 24.
Exhaustive enumeration for m = 11 hit two computational barriers:
- Generating the regular catalogue RSMU(n,11) requires a non-public modification of McKay's
genbgbipartite graph generator, which cannot run under stock nauty. - The shortest-proof SAT encoding for m = 11 at proof sizes s ≥ 27 exceeds budget limits.
Reconciling the singular candidate census for hardness 29 established the correct total of 626,973 candidates and exposed the missing RSMU(8,10) directory in the public Zenodo release.
Discussion
This entry carries CAVEAT status: h_11 remains unresolved, and no new hardness bound was established.
The primary contributions are verification through m = 9 and catalogue corrections. The Zenodo archive omits RSMU(8,10), and the candidate census was rectified to 626,973.
An untried route around the generator bottleneck is to build an orderly generator at the formula level and precalculate h(base) across all 73,517 bases to prune candidates before SAT encoding.
For everyone — the takeaway
What this means
Pinning down exact proof size bounds for small formulas gives baseline targets for automated reasoning and SAT solver design. When formula spaces explode combinatorially, missing files and miscounts derail follow-up experiments. Fixing the candidate census to 626,973 and noting the missing RSMU(8,10) dataset clears the ground for future proof complexity work.
Attribution and prior art
Prior art: Prior work by Peitl-Szeider established the values of h_m for m ≤ 10 (including h_10 = 26) and proved that h_11 ≥ 28. Sources: Peitl, Szeider 2021 (JAIR) · Peitl, Szeider, short-proof code
Register references
- ML-095
- Peitl-Szeider (prior art establishing h_m for m ≤ 10 and h_11 ≥ 28)
- Verification receipt:
lanes/hardness-h11/VERIFY.md - Wall receipt:
lanes/hardness-h11/WALL.md - Execution box:
frontier/h11/
Every artifact named above is bundled in, or hashed by, this paper's evidence pack below.
Evidence pack
Everything needed to check this entry against its receipts: the register text, a manifest with a SHA-256 hash for every named receipt, and 2 of 2 receipt files bundled (8 KB). Anything not bundled is still hashed in the manifest and lives in the compute-box working trees.
Changelog
Last reviewed 2026-09-06
- 2026-09-06Published on this site.