OpenAI's Exponential Time Hypothesis Claim: What It Does and Does Not Prove

OpenAI announced on October 26 that its AI had disproved the Exponential Time Hypothesis, a major assumption about computational difficulty. It released a manuscript and Lean formalization for public examination. The claim matters for algorithm research, but it does not establish that P equals NP or that today's software suddenly runs faster.

What the Exponential Time Hypothesis means

The Exponential Time Hypothesis, usually shortened to ETH, concerns 3-SAT. This is a problem where a computer must decide whether values can be assigned to Boolean variables so that a collection of logical conditions is satisfied.

In the standard formulation, ETH says there is no algorithm for n-variable 3-SAT with subexponential running time. The tutorial by Russell Impagliazzo explains how this assumption supports more detailed questions about computational difficulty than simply asking whether a problem is NP-hard.

The important word is “subexponential”. It describes how the required work grows as the input becomes larger. It does not mean that the work is small, or that an implementation will outperform an existing solver on the cases a business actually encounters.

What OpenAI has released

In its public announcement, OpenAI says the natural-language result was obtained on October 16 and formalized in Lean the next day. October 26 is the public announcement date, not the date the model first produced it.

A group led by Russell Impagliazzo, Ramamohan Paturi and Ryan Williams will examine and explain the work. OpenAI says participation is independent, voluntary and unpaid, and that the materials are public to support broader verification. The announcement presents this as the beginning of a research process, not its conclusion.

The company's repository describes these model outputs as research artifacts rather than polished academic papers. That is a useful reading instruction: a released artifact is something researchers can inspect, compare and explain, not a substitute for that work.

What the formalization actually covers

The published Lean scope document describes a deterministic machine that exactly counts satisfying assignments for canonically encoded Boolean formulas in conjunctive normal form, with a fixed maximum clause width. Its time bound is subexponential in the number of variables, multiplied by a polynomial in the encoding length. It also bounds visited tape cells polynomially in that length.

Counting answers is stronger than merely deciding whether at least one answer exists. However, the input encoding, fixed clause width and precise resource bounds are part of the statement. Leaving those out would make the result sound broader and less specific than the released documentation.

There is also a difference between the artifacts. The scope page lists a sharper running-time bound in the October 25 manuscript than in the Lean formalization's stated guarantee. That means “the paper” and “the formalized result” should not be treated as interchangeable descriptions of every bound.

I have not independently checked or rebuilt the proof. Reporting that OpenAI released a Lean formalization is different from claiming to have verified its correctness, its assumptions or its correspondence with the natural-language argument.

Does disproving ETH prove P equals NP?

No. Subexponential time does not imply polynomial time. As an illustration, a running time proportional to two raised to the square root of the input size is subexponential, yet grows faster than every fixed polynomial. That example is not the running-time bound of this release; it shows why the distinction matters.

An ETH disproof can therefore change a particular boundary believed to limit algorithm design without settling the wider P versus NP question. It would also change how researchers interpret conclusions that explicitly depend on ETH. It would not automatically erase every hardness result about the same problems, especially results derived from other assumptions or proved unconditionally.

For software teams, an asymptotic theorem is not a deployment benchmark. Constants, input sizes, memory use, implementation complexity and the structure of real workloads all matter. A result about eventual growth can be important even before it yields a useful production algorithm.

What to watch next

The most useful next evidence will be the independent group's explanation of the mechanism, the exact statement that survives scrutiny, and which algorithmic consequences can actually be derived from it. Those are more informative than treating the headline as a general promise of faster computing.

For AI-assisted research, this release also makes the handoff visible. Producing a candidate result, checking a formal statement and developing an explanation that other scientists can use are separate pieces of work. The value grows when researchers can move reliably between all three.

I’m Paras. I work at the intersection of AI, engineering and distribution.

I help technical teams turn complex AI research and product updates into clear stories developers and founders can understand and share.

Book a 30-minute call