The exponential time hypothesis (ETH) asserts an exponential lower bound for deterministic algorithms deciding 3SAT. Let count the variables and
denote the input length, and use
for big-O notation, so that
denotes a factor bounded by a fixed power of
. Formally, ETH asserts that there is a constant
such that no deterministic algorithm decides 3SAT
in time
(Impagliazzo and Paturi 2001). In particular, it rules out a running time of , where
denotes a quantity whose ratio to
tends to 0 (little-o
notation).
A 3SAT instance is a conjunctive normal form formula with at most three literals per
clause. More generally, -SAT allows at most
literals per clause.
Equivalently, for each fixed
,
there are constants
and
such that no deterministic algorithm
solves
-SAT
with at most
clauses in time
(Impagliazzo and Paturi 2001, Impagliazzo
et al. 2001). Thus the hypothesis distinguishes among superpolynomial
running times, rather than merely asserting that 3SAT
is not solvable in polynomial time. ETH implies
a negative answer to the P versus NP problem,
but the converse is not known.
OpenAI (2026a) reported a deterministic algorithm that, for each fixed ,
counts the satisfying assignments of a conjunctive
normal form formula with at most
literals per clause.
In the bound below,
is the number of variables,
is the number of clauses, and
is big-O notation whose
implicit constants and asymptotic thresholds may depend
on the fixed parameter
,
but not on
or
. The algorithm uses polynomial
space and has bit complexity
The documented Lean bound instead has exponent , which is also
. Either bound would refute ETH, but neither would
establish that P equals NP. An internal OpenAI model supplied the reported proof
and Lean formalization. Impagliazzo et al. (2026) invited community examination
of the OpenAI claim and explicitly distinguished their involvement from certification
of the proof. An external audit of OpenAI's Lean formalization
reported rebuilding its 3,977-module development for the weaker bound, finding only
Lean's three standard axioms, and comparing the proved
statement and its definitions with the formal target (Zhao 2026). The statement readings
used Claude models. The correspondence with standard Turing
machines and input encodings was not formally checked.
Busnello (2026) also reported acceptance of OpenAI's formal proof
by Lean's default kernel in an external comparator run. O'Donnell (2026) presents
an LLM-assisted exposition of OpenAI's argument using exact evaluation of permanents
of rational matrices with a bounded number of
nonzero entries in each row and column. Kintali (2026) presents a simplified 3SAT
decision argument using polynomial interpolation.
Independent specialist confirmation of the complete mathematical claim had not been
reported as of Nov. 1, 2026.
Claude (2026) reported a separate deterministic algorithm for counting satisfying assignments of -SAT formulas in time
for each fixed
. The accompanying Lean statement includes this
bound on a deterministic Turing machine. It covers
formulas with
variables and at least
two clauses, with no repeated clauses
and every variable occurring. An internal research Claude
model at Anthropic discovered the algorithm, and AI
models wrote its formalization. In addition to the project's automated checks, Busnello
(2026) reported external acceptance of the formal proof
by both Lean's default kernel and nanoda. Both main declarations depended only on
Lean's three standard axioms. The check did not establish
correspondence with the paper or verify the simulation and formula rewriting that
connect its machine model to the usual formulation of ETH. Independent specialist
confirmation of the complete claim had not been reported as of Nov. 1, 2026.