On October 26, 2026, OpenAI committed a 67-page manuscript to its public repository with an unmistakable title: The Exponential Time Hypothesis is False. The author list contained a single designation: “OpenAI”. Accompanying the paper was a complete, machine-checkable formal proof in Lean.
For 27 years, the Exponential Time Hypothesis (ETH) stood as the bedrock beneath hundreds of conditional lower bounds across theoretical computer science. Now, it has been directly dismantled by a deterministic algorithm. Rather than declaring an isolated corporate victory, OpenAI invited the original architects of the hypothesis to spearhead an independent evaluation network. At the frontier of theoretical inquiry, the burden of comprehension and governance has decisively returned to human peer institutions.
A Deterministic Algorithm Compresses 3-SAT Complexity into Subexponential Time
Formulated in 1999 by Russell Impagliazzo and Ramamohan Paturi, the Exponential Time Hypothesis conjectures that solving 3-SAT requires $2^{\Omega(n)}$ time in the worst case. Over nearly three decades, complexity theorists constructed an expansive scaffolding of conditional lower bounds on this foundation. The widely accepted barrier preventing subexponential solutions for a vast swath of NP-complete problems relied entirely on this unproven perimeter.
OpenAI’s Theorem 1.1 reshapes that landscape. The theorem establishes a deterministic algorithm that computes the exact number of satisfying assignments for any $k$-CNF formula with fixed $k \ge 2$. Its running time is bounded by $(n+m)^{O_k(1)} \cdot 2^{O_k(\sqrt{n \log \log n / \log n})}$. When the clause density satisfies $m \le Dn$, this upper bound further contracts to $2^{O_{k,D}(\sqrt{n/\log n})}$.
Figure: The paper’s first page features the singular OpenAI authorship and abstract, highlighting subexponential time bounds and refuting the Exponential Time Hypothesis. Source: GitHub (openai/math repository)
Mathematically, the running time is strictly $2^{o(n)}$, directly invalidating the core exponential barrier posited by ETH. Crucially, the deterministic algorithm does not merely decide satisfiability; it performs exact model counting within polynomial space. By exploiting algebraic structure to resolve Boolean constraints, the algorithm circumvents the combinatorial bottlenecks inherent to traditional search heuristics.
The technical architecture synthesizes exact counting, sparse parity testing, and polynomial interpolation. At its center lie “shared linear sketches” combined with low-degree polynomial replacement. The structural implications ripple outward immediately: Max-$k$-SAT can now be approximated to within $OPT(F) - \varepsilon m$ in subexponential time.
Lower bounds across graph theory have shifted in tandem. Counting independent sets and graph coloring with a fixed number of colors now run in $2^{o(v)}$ time, while exact counting of perfect matchings drops deterministically to $2^{o(v+e)}$. A constellation of conditional hardness results rooted in ETH has simultaneously dissolved, compelling researchers to recalculate the fine-grained boundaries of computational tractability.
Theoretical Boundaries: Why the Subexponential Bound Does Not Imply P=NP
Shifts in fundamental complexity assumptions routinely invite conceptual drift. Following the upload, online communities immediately speculated whether the result hinted at $P=NP$—a misunderstanding driven by the subtleties of asymptotic reduction. Addressing these misinterpretations, the authors included an explicit clarification on page 2.
Figure: Page 2 presents the main theorem and algorithm bounds alongside an explicit statement confirming that this subexponential bound cannot propagate across all of NP via standard reductions. Source: GitHub (openai/math repository)
The manuscript clarifies that a $2^{o(n)}$ running time does not transfer across standard polynomial-time reductions. Extending subexponential upper bounds to arbitrary NP problems would demand a significantly tighter $2^{n^{o(1)}}$ rate. The breakthrough bears no direct bearing on the $P \text{ vs } NP$ question, and OpenAI makes no claim to that effect.
The authors characterize the manuscript as “raw research data.” Although the Lean repository provides a fully mechanized formal proof, symbolic verifiability is not interchangeable with human understanding. Machine-checked lines eliminate syntactic loopholes, but they cannot articulate why a specific combination of interpolation steps succeeds. The paper still requires peer mathematicians to distill intuitive geometric and combinatorial models from raw proof artifacts.
Lean ensures that each deductive step is formally sound. Yet, mechanized verification can rule out logical flaws without imparting deep algorithmic insight. In this vacuum, human mathematical synthesis remains indispensable.
Inviting Conjecture Founders to Lead the Review
Departing from conventional industry communications, OpenAI bypassed unilateral publicity. Alongside the paper, the team announced a distinguished steering committee invited to lead the evaluation. The core group includes Russell Impagliazzo, Ramamohan Paturi, and Ryan Williams.
The selection carries profound symbolic and academic weight. Impagliazzo and Paturi formulated ETH in 1999 alongside Francis Zane, while Williams famously leveraged circuit lower bounds years later to refute the Strong Exponential Time Hypothesis for ACC$^0$. By entrusting verification to the conjecture’s creators and its most accomplished investigators, institutional posturing gave way to rigorous collective scrutiny.
To ensure the independence of this review network, OpenAI contributed $5 million in unrestricted funding to the Simons Foundation, anchoring a $15 million theoretical research collaboration. These resources will fund workshops and dedicated research sabbaticals, giving external scholars the runway needed to audit every mathematical lemma.
This deliberate governance model directly reflects lessons learned two weeks prior. On October 6, OpenAI released a batch of 722 unfiltered AI manuscripts, drawing sharp criticism from leading mathematicians including Terence Tao. Critics warned that flooding preprint ecosystems with low-confidence claims creates unnecessary drag on limited peer-review resources.
Tri-Track Verification Across Three Disciplines
In its October 26 disclosure, OpenAI released three separate theoretical contributions, each mapped to a distinct verification mechanism tailored to the epistemic demands of the field:
For computer science, the ETH refutation followed an “open code plus external steering” framework, pairing Lean formal proofs with public preprints for immediate global scrutiny.
In harmonic analysis, a proof addressing the local smoothing conjecture for the Euclidean wave equation was released directly into open community evaluation. Generated on October 18 and verified in Lean on October 19, the paper proves Christopher Sogge’s 1991 conjecture across all dimensions, subsuming longstanding problems such as the Kakeya and Stein restriction conjectures without a dedicated committee.
Figure: The first page of the harmonic analysis paper released simultaneously, presenting an all-dimension proof for the local smoothing conjecture. Source: GitHub (openai/math repository)
For high-energy theoretical physics, OpenAI adopted strict containment. A claimed proof concerning the existence of interacting four-dimensional quantum field theories—directly touching the Yang-Mills Millennium Prize Problem—was transferred entirely to an independent external panel led by 2004 Nobel laureate David Gross, alongside Michael Douglas and Arthur Jaffe. The external committee holds complete discretion over when and how model details and derivations are made public.
These three tracks reflect four operating principles: maintaining full transparency, abstaining from academic co-authorship for foundational models, ensuring external autonomy, and matching review structures to theoretical risk. Calibrating governance to the epistemic thresholds of distinct disciplines represents an experiment in how frontiers of machine-generated knowledge should be steered.
The Shifting Human Role: From Derivation to Adjudication
The trajectory from initial text generation on October 16 to verified Lean formalization on October 17 spanned barely 48 hours. What took theoretical computer science nearly three decades to construct was dismantled in hours of automated symbolic search. This velocity outpaces standard academic review timelines, placing severe strain on conventional publishing pipelines.
Yet code passing a Lean compiler proves only that symbolic premises align with derivation rules. It does not dissolve the intellectual friction human researchers encounter when grasping why an algorithm works. Synthesizing conceptual frameworks and geometric intuition will still take months of collective scholarly labor. Automated tools can build airtight deductive chains; they cannot comprehend them on our behalf.
As a consequence, the division of labor in advanced research is undergoing a structural realignment. With proof construction and symbolic checking increasingly automated, the bottleneck shifts away from iterative calculation. The primary responsibility of human scholars pivots decisively toward intuition extraction, conceptual critique, and ultimate adjudication.
Regardless of whether this 67-page paper survives exhaustive peer audit, the traditional paradigms of scientific production have irrevocably shifted. By seating the conjecture’s founders at the center of the review, OpenAI acknowledged that algorithmic output cannot unilaterally establish scientific consensus. In exploring complex domains, machines may reach logical destinations first—but the authority to determine whether a breakthrough truly holds remains firmly in human hands.
Reference Links:
- OpenAI Research: The Exponential Time Hypothesis is False manuscript and Lean formalization repository
- OpenAI Research: Local smoothing for the Euclidean wave equation manuscript
- Simons Foundation: Collaboration Announcement on Frontiers in Theoretical Computer Science and Mathematics
