Consequences of the ETH refutations for proof complexity and knowledge compilation

The Exponential Time Hypothesis was recently refuted by two counting algorithms, one from OpenAI and one from Anthropic. We describe consequences of the refutations for proof complexity and for knowledge compilation. Both follow from one intermediate result: the weighted model count of every 3-CNF on n variables has an arithmetic circuit of size 2^(o(n)), which can be chosen smooth and decomposable. We obtain these circuits from the identities used in the Anthropic preprint to prove its counting algorithm correct, and we take three statements of the preprint as given. Lean 4 checks the derivation of the circuits from these three statements. For proof complexity, it follows that every unsatisfiable 3-CNF on n variables has a refutation of size 2^(o(n)) in the Ideal Proof System (IPS) of Grochow and Pitassi, over every field of characteristic other than 2, and Lean checks this size bound as well. We sketch how to obtain such refutations in characteristic 0 from the OpenAI preprint. If Extended Frege polynomially simulates IPS over F_p for an odd prime p, then it also refutes every unsatisfiable 3-CNF in this size. By known lower bounds, no such size bound is possible for resolution, Res(k) for fixed k, polynomial calculus, or sum-of-squares. For knowledge compilation, we show that a monotone circuit (with addition and multiplication gates and nonnegative real constants) for the weighted model count of a satisfiable CNF yields a complete DNNF of the formula with at most as many gates, and Lean checks this lemma. By a lower bound of de Colnet and Mengel, complete DNNFs of Tseitin formulas of expanders of maximum degree 3, and hence monotone circuits for their weighted model counts, need exponentially many gates. Our circuits for these formulas are smaller for large n, so circuits of their size must contain negative constants. We prove this corollary, like the one on Extended Frege, on paper. We also give a lower bound for monotone circuits for the clique polynomial that the Anthropic algorithm evaluates, and Lean checks it. For suitable parameters, we obtain circuits below this bound from the same identities. The size bounds for 3-CNFs are asymptotic. Both algorithms are galactic, and we establish no improvement over exhaustive search at physical sizes. Files: eth_consequences_note.pdf (the note, 14 pages), eth_consequences_companion.pdf (the Companion, 18 pages, with the precise assumptions, the statements checked in Lean and the paper proofs) and eth_consequences_supplement.zip (the Lean 4 project and four scripts that test the identities and the assumptions on small instances). Earlier records: https://doi.org/10.5281/zenodo.23688831 (the OpenAI thresholds), https://doi.org/10.5281/zenodo.23797196 (the k×k Clique Hypothesis) and https://doi.org/10.5281/zenodo.23981771 (the klam value).

Authors

Institutions

Publication Details

Journal
Zenodo (CERN European Organization for Nuclear Research)
Published
2026-11-15
DOI
https://doi.org/10.5281/zenodo.24243987
Primary Topic
Complexity and Algorithms in Graphs
Type
article
Field-Weighted Citation Impact
0.00
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
article

Consequences of the ETH refutations for proof complexity and knowledge compilation

Stefan Szeider
Zenodo (CERN European Organization for Nuclear Research)
Complexity and Algorithms in Graphs
article

Consequences of the ETH refutations for proof complexity and knowledge compilation

Stefan Szeider
article en

Abstract

The Exponential Time Hypothesis was recently refuted by two counting algorithms, one from OpenAI and one from Anthropic. We describe consequences of the refutations for proof complexity and for knowledge compilation. Both follow from one intermediate result: the weighted model count of every 3-CNF on n variables has an arithmetic circuit of size 2^(o(n)), which can be chosen smooth and decomposable. We obtain these circuits from the identities used in the Anthropic preprint to prove its counting algorithm correct, and we take three statements of the preprint as given. Lean 4 checks the derivation of the circuits from these three statements. For proof complexity, it follows that every unsatisfiable 3-CNF on n variables has a refutation of size 2^(o(n)) in the Ideal Proof System (IPS) of Grochow and Pitassi, over every field of characteristic other than 2, and Lean checks this size bound as well. We sketch how to obtain such refutations in characteristic 0 from the OpenAI preprint. If Extended Frege polynomially simulates IPS over F_p for an odd prime p, then it also refutes every unsatisfiable 3-CNF in this size. By known lower bounds, no such size bound is possible for resolution, Res(k) for fixed k, polynomial calculus, or sum-of-squares. For knowledge compilation, we show that a monotone circuit (with addition and multiplication gates and nonnegative real constants) for the weighted model count of a satisfiable CNF yields a complete DNNF of the formula with at most as many gates, and Lean checks this lemma. By a lower bound of de Colnet and Mengel, complete DNNFs of Tseitin formulas of expanders of maximum degree 3, and hence monotone circuits for their weighted model counts, need exponentially many gates. Our circuits for these formulas are smaller for large n, so circuits of their size must contain negative constants. We prove this corollary, like the one on Extended Frege, on paper. We also give a lower bound for monotone circuits for the clique polynomial that the Anthropic algorithm evaluates, and Lean checks it. For suitable parameters, we obtain circuits below this bound from the same identities. The size bounds for 3-CNFs are asymptotic. Both algorithms are galactic, and we establish no improvement over exhaustive search at physical sizes. Files: eth_consequences_note.pdf (the note, 14 pages), eth_consequences_companion.pdf (the Companion, 18 pages, with the precise assumptions, the statements checked in Lean and the paper proofs) and eth_consequences_supplement.zip (the Lean 4 project and four scripts that test the identities and the assumptions on small instances). Earlier records: https://doi.org/10.5281/zenodo.23688831 (the OpenAI thresholds), https://doi.org/10.5281/zenodo.23797196 (the k×k Clique Hypothesis) and https://doi.org/10.5281/zenodo.23981771 (the klam value).

Zenodo (CERN European Organization for Nuclear Research)
TU Wien (AT)
Complexity and Algorithms in Graphs
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon