OpenAI AI Disproves 1998 Exponential Time Hypothesis

OpenAI has announced an AI-generated disproof of the Exponential Time Hypothesis, a 28-year-old conjecture in computational complexity theory, in a 67-page paper officially launched on October 26, 2026. Russell Impagliazzo, who co-proposed the hypothesis in 1998, called the result "very shocking news," according to The New York Times. The claim arrives alongside a separate 49-page proof from Anthropic, both presenting algorithms for the 3-SAT problem with running time 2^o(n), verified by the Lean proof checker.

Release Date and Verification Timeline

Officially released on October 26, 2026, OpenAI's paper states its AI discovered the natural-language disproof on October 16 and formalized the proof the following day. Anthropic published its companion result the same day. Both organizations say their proofs passed machine verification in Lean, a program that checks mathematical proofs line by line for logical errors. The proofs are now under human expert review by a team including MIT's Ryan Williams, Impagliazzo, and Ramamohan Paturi of UC San Diego.

What the Exponential Time Hypothesis Claims

The Exponential Time Hypothesis, proposed in 1998, conjectures that no algorithm can solve 3-SAT, a fundamental problem in computer science, significantly faster than brute-force exponential time. A disproof demonstrates an algorithm running in 2^o(n) time, meaning the exponent grows slower than linearly with problem size. The hypothesis underpins hardness assumptions across cryptography, algorithm design, and computational complexity theory. Impagliazzo noted that most researchers expected stricter versions of the hypothesis to fall first, making this result particularly surprising.

Practical Limits of the Speedup

The theoretical breakthrough does not translate to immediate practical gains. Outside estimates cited by the Times place OpenAI's verified speedup advantage beyond roughly 10 to the power of 2,389 variables, an astronomically large threshold. Anthropic wrote that its method, applied to 3-SAT formulas with five clauses per variable, would not outperform brute force until problems exceeded 10^10,000 variables, far beyond any storable computation. Neither organization claims the result directly resolves whether P equals NP, and OpenAI stated the speedup does not extend to NP problems generally.

Expert Reaction and Review Process

Ryan Williams told TechCrunch the proofs contain "two or three alien-looking parts" that prompted him to believe the entire research community should collaborate on understanding them. The co-proposers issued a joint statement clarifying that "our involvement should not be taken as certification of the claim." Williams confirmed the review group signed no non-disclosure agreements and will not receive payment. He asked OpenAI to release all raw data on the result and fund a conference for the research community. OpenAI agreed to both requests.

Long-Term Implications for Chip Design and Encryption

Williams suggested a validated disproof could eventually accelerate chip design and weaken current encryption standards, though he emphasized any practical payoff remains years away. The techniques introduced in both papers may offer insights for algorithm development even if the immediate computational advantage is unreachable. OpenAI and Anthropic's use of AI to generate and formalize complex mathematical proofs represents a new frontier in automated reasoning, with potential applications across domains requiring rigorous verification.

What This Means

OpenAI's AI-generated disproof of the Exponential Time Hypothesis marks a significant moment in computational complexity theory, challenging assumptions held for nearly three decades. While practical applications are distant, the result demonstrates AI's growing capability to tackle problems at the frontier of human mathematical knowledge. The community review process and OpenAI's commitment to data transparency will determine whether the claim withstands scrutiny and what new algorithmic techniques emerge from the "alien-looking" methods embedded in the proofs.