On 26 October 2026 OpenAI announced three results produced by its internal models. The most relevant for anyone who works with software is an algorithm that, if the ongoing verification confirms it, refutes the Exponential Time Hypothesis (ETH), one of the hypotheses on which much of computational complexity has rested for more than twenty-five years. It follows the 6 October release I wrote about in Is the world we knew really over?.

P, NP and where the ETH sits

P is the class of problems an algorithm can solve in polynomial time, with a number of steps that grows as a power of the input size (n2, n3…). NP is the class of problems where a proposed solution can be checked in polynomial time, even if finding it may take far longer.

The reference example is SAT (satisfiability). Given n variables that are true or false, combined with “and”, “or” and “not” as in (x₁ or not x₂) and (x₂ or x₃), the question is whether some assignment makes the formula true. Checking one is immediate, while finding one may mean trying 2n combinations, more than 1030 with a hundred variables. In its 3-SAT version, with three variables per bracket, the problem is NP-complete: every problem in NP can be translated into it, so a polynomial algorithm for 3-SAT would give P = NP.

The ETH, formulated between 1999 and 2001 by Russell Impagliazzo, Ramamohan Paturi and Francis Zane, goes beyond P ≠ NP: it states that 3-SAT requires exponential time in the worst case, 2Ω(n). It was never proved, but together with its strong version, SETH, it became the foundation of hundreds of hardness bounds in fine-grained complexity, the field that asks exactly which exponent a problem needs.

The new result

The paper presents a deterministic algorithm that counts the solutions of any k-CNF formula with n variables in time 2O(n log log n / √log n) up to polynomial factors, that is, subexponential time. The technique is algebraic: the formula becomes a polynomial, and counting reduces to the common zeros of systems of sparse polynomial equations. The model produced the refutation on 16 October and the Lean formalization on the 17th. The paper and the proof are public, and verification has been entrusted to a group led by Impagliazzo, Paturi and Ryan Williams.

If the theorem holds, ETH and SETH fall. P versus NP remains open, because 2n/√log n still grows faster than any polynomial. Many fine-grained bounds lose one foundation but not all of them, since several also follow from weaker hypotheses such as the Orthogonal Vectors Conjecture. The hidden constants are not known, and OpenAI itself writes that practical benefits will require significant further research.

The other two results are a proof in every dimension of Christopher Sogge’s local smoothing conjecture and the rigorous existence of quantum chromodynamics and pure Yang–Mills theory, without the mass gap required by the Millennium Prize problem.

What I think

AI is confirming something we could not see clearly: exponential phenomena remain hard for people to grasp. It holds for the growth of AI itself: according to METR, the length of tasks models complete on their own doubles roughly every seven months. If the trend continued, five years would mean eight and a half doublings, a factor of almost 400. It holds for pandemics and for viral phenomena. And it holds for the ETH: if the result stands, for more than twenty-five years the boundary between exponential and subexponential in one of computer science’s most studied problems was placed in the wrong spot.

The difficulty has been measured. In 1975 Wagenaar and Sagaria observed that often two thirds of participants estimated exponential growth at below 10% of the correct value. In 2020 Lammers, Crusius and Gast found the same error for coronavirus infections: people pictured linear growth. According to Stanislas Dehaene, our spontaneous intuition of numbers is logarithmic and the linear scale is learnt at school.

The ETH case shows that the boundary is hard to see even for those who study it for a living. As a rough indication, with base-2 logarithms and ignoring constants, for a formula with a million variables the exponent of the new algorithm is still about n, the same as exhaustive search. Halving it takes about 1077 variables, a number close to that of the atoms in the observable universe. Exponential and subexponential part ways at scales no direct experience reaches. Intuition does not get there, and proofs are needed.

And yet we are the product of phases of very fast growth, such as the Cambrian explosion and the other evolutionary radiations that multiplied forms of life within short spans on a geological scale. The theory of punctuated equilibria by Niles Eldredge and Stephen Jay Gould, still debated, describes evolution as long periods of stability interrupted by brief accelerations. They happen over millions of years, though, while our intuition is calibrated on the span of a life, and often on just a few days.

If intuition is not enough, we need tools that extend it. Repeated measurements like METR’s make growth visible before it becomes obvious. A proof in Lean lets us verify that a subexponential algorithm exists even when intuition does not see it. I believe this is the role of the human part in a governed superintelligence: deciding what matters, verifying and answering for the results.

Cover image: a nautilus shell in cross-section. Each new chamber is larger than the previous one by the same ratio, and together they trace a logarithmic spiral: exponential growth produced by evolution. Photo by Chris 73 on Wikimedia Commons — CC BY-SA 3.0 — https://commons.wikimedia.org/wiki/File:NautilusCutawayLogarithmicSpiral.jpg — licence: https://creativecommons.org/licenses/by-sa/3.0/