Disproof of the Exponential Time Hypothesis

1 · The essentials

The manuscript studies problems in which each variable can be true or false and a collection of rules determines which choices are allowed. Each rule involves at most a fixed number of variables. Rather than merely finding out whether any choice works, the algorithm counts exactly how many choices work. The manuscript reports a running time whose exponential part grows more slowly than two raised to any fixed positive multiple of the number of variables. It also reports that the memory required grows only polynomially with the size of the input. This contradicts the Exponential Time Hypothesis, which says that even deciding whether a choice works can require such exponential time when rules involve at most three variables. The main result has a Lean formalization.

A picture to help (an imperfect image, not to be taken literally)

As an imperfect image, imagine a panel of on/off switches with many restrictions, each involving only a fixed number of switches. The task is to count all permitted panel settings, not just find one; the manuscript reports an algorithm with a better worst-case growth rate than the stated hypothesis would allow even for finding out whether a permitted setting exists.

Why it matters

The stated result directly contradicts ETH, a hypothesis about the worst-case difficulty of deciding 3-SAT. Exact counting answers the decision question as well: a satisfying assignment exists precisely when the count is nonzero. The repository summary also reports a consequence for circuit complexity: superlinear circuit lower bounds for a language in $E^{NP}$ on infinitely many input lengths.

2 · Going further

The input is an arbitrary $k$ -CNF formula with $n$ variables and $m$ clauses, where $k \geq 2$ is fixed. A CNF formula is a collection of clauses that must all hold, with each clause allowing a disjunction of literals; here each clause has at most $k$ literals. The task is to count exactly the assignments satisfying the whole formula. The manuscript reports a deterministic algorithm using polynomial space in $n$ and $m$ and time $(n + m)^{O_{k} (1)} 2^{n / (l o g n)^{1/2 + o (1)}}$ . The notation $O_{k} (1)$ permits the polynomial exponent to depend on the fixed clause-width bound $k$ .

The supplied abstract states ETH as the assertion that deciding 3-SAT on $n$ variables requires $2^{Ω (n)}$ time in the worst case. Taking $k = 3$ and checking whether the exact count is nonzero connects the counting algorithm to that decision problem. In the reported bound, the exponent of the exponential factor is sublinear in $n$ ; the manuscript presents the resulting algorithm as a refutation of ETH.

The abstract gives the algorithm's guarantees but does not describe its construction or the main technical steps of its argument. The main manuscript is marked as Lean-formalized, while no more detailed formalization scope is supplied. The repository summary additionally reports superlinear circuit lower bounds for a language in $E^{NP}$ on infinitely many input lengths, but supplies neither an argument for this consequence nor any companion-manuscript abstracts explaining the connection.

Useful notions

True-or-false variables and assignments
Clauses and CNF formulas
Counting versus deciding existence
Worst-case running time and space
Polynomial and exponential growth

What was known before / what is new

Before

The source describes ETH as postulating a worst-case $2^{Ω (n)}$ time requirement for deciding 3-SAT on $n$ variables. It provides no account of earlier algorithms, earlier lower bounds, or the historical development of the hypothesis.

New

The main manuscript reports deterministic exact counting for every fixed $k \geq 2$ with the stated running-time bound and polynomial space, and presents this as a refutation of ETH. The main result has a Lean formalization. The repository summary also reports the circuit-lower-bound consequence, without supplying its derivation.

Limits and assumptions

The guarantee applies to every fixed $k \geq 2$ ; it is not stated as a uniform bound with the same polynomial exponent when $k$ grows with the input. The running time retains a polynomial factor in both $n$ and $m$ , and the reported exponential factor is not a polynomial-time bound. The main result is Lean-formalized, but the supplied material does not specify which additional claims the formalization covers, so verification of the circuit consequence should not be inferred. That consequence is stated only for infinitely many input lengths, not all lengths. The source identifies no remaining open questions and provides no algorithmic details beyond the guarantees in the abstract.

Mini glossary

Satisfying assignment: A choice of true or false for each variable that makes every clause of a formula hold.
$k$ -CNF: A formula consisting of clauses that must all hold, each containing at most $k$ literals, where a literal is a variable or its negation.
Deterministic algorithm: An algorithm whose execution is fixed by its input rather than by random choices.
Polynomial space: A memory requirement bounded by a polynomial in the input-size parameters, here $n$ and $m$ .
Exponential Time Hypothesis: The hypothesis stated in the source that deciding 3-SAT on $n$ variables requires $2^{Ω (n)}$ time in the worst case.
Superlinear circuit lower bound: A bound asserting that the required circuit size grows faster than linearly with input length.

Keywords : Exact counting · Exponential Time Hypothesis · Circuit lower bounds

AI-generated explanation based on the manuscript. Unofficial. Refer to the manuscript for the authoritative version.

3 · Technical details and sources

Claim made in the manuscript (source text)

For every fixed $k \geq 2$ , a deterministic algorithm counts the satisfying assignments of a $k$ -CNF with $n$ variables and $m$ clauses in time $(n + m)^{O_{k} (1)} 2^{n / (l o g n)^{1/2 + o (1)}}$ . This yields superlinear circuit lower bounds for a language in $E^{NP}$ on infinitely many input lengths.

Verified by Lean: the Lean software checked the part of the reasoning described below, sometimes only part of the manuscript. This does not mean independent mathematicians have validated the result.

Scope of the Lean formalization (source text)

…

lean/docs/378.md

Manuscripts in this family

★

The Exponential Time Hypothesis is False

25/10/2026

Verified by Lean

We give a deterministic algorithm for exactly counting the satisfying assignments of an arbitrary $k$ -CNF formula. For every fixed $k \geq 2$ , on a formula with $n$ variables and $m$ clauses, our algorithm uses space polynomial in $n$ and $m$ and runs in time $(n + m)^{O_{k} (1)} 2^{n / (l o g n)^{1/2 + o (1)}}$ . Our algorithm refutes the Exponential Time Hypothesis (ETH), which postulates that deciding 3-SAT on $n$ variables requires $2^{Ω (n)}$ time in the worst case.

PDF GitHub folder Lean formalization