Hard CNF Instances for Ideal Proof Systems
Tuomas Hakoniemi, Nutan Limaye, Iddo Tzameret · 2026
Read Hard CNF Instances for Ideal Proof Systems by Tuomas Hakoniemi, Nutan Limaye, Iddo Tzameret (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-04544.txt.
Description
Tuomas Hakoniemi, Nutan Limaye, and Iddo Tzameret prove lower bounds for a powerful algebraic proof system. Their test cases are formulas in conjunctive normal form, the standard format of basic logic. The Ideal Proof System verifies that a set of polynomial equations has no solution. Researchers had bounded its size for many algebraic formulas, but not for logical ones.
That gap was a central open problem. It separated the algebra side from the logical statements that proof complexity ultimately cares about. For a restricted but important version of the system, based on read-once branching programs, the authors resolve it. They use a rank-based interpolation argument. It shows certain hard logical formulas genuinely require large refutations.
Catalog record
| CREATOR | Tuomas Hakoniemi, Nutan Limaye, Iddo Tzameret |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 102 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.04544