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

CREATORTuomas Hakoniemi, Nutan Limaye, Iddo Tzameret
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE102 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.04544

Browse the full library · About the Tower of Babel