OpenAI claims to have disproved the exponential time hypothesis — a 25-year pillar of computer science

OpenAI Claims to Have Disproved the Exponential Time Hypothesis

OpenAI announced three new discoveries spanning mathematics, computer science, and physics. The most significant claim: an internal model has disproved the exponential time hypothesis (ETH), a foundational assumption in theoretical computer science that has stood for roughly 25 years.

What ETH says—and why it matters

The exponential time hypothesis rests on a famous puzzle in computer science called 3SAT. Given a long list of yes-or-no switches and a set of rules about how they must be arranged, the goal is to find a combination that satisfies every rule. The obvious brute-force approach—trying every combination—doubles the number of possibilities with each new switch. A puzzle with a few hundred switches would take longer than the age of the universe to solve this way.

For 25 years, computer scientists found clever tricks that made solving 3SAT somewhat faster, but every trick hit the same wall: time required still exploded exponentially as the puzzle grew. In the late 1990s, Russell Impagliazzo, Ramamohan Paturi, and Francis Zane formalized this wall into the exponential time hypothesis: no algorithm, however brilliant, will ever solve 3SAT without the time blowing up exponentially. Nobody proved it, but the field treated it as a law of nature. Hundreds of research papers across scheduling, graphs, logic, and other domains rest on ETH as a measuring stick—if you could show that solving some other problem quickly would also crack 3SAT quickly, you had shown that problem was hopelessly hard too.

The claim

OpenAI's model claims to have found an algorithm that solves these puzzles meaningfully faster than ETH allows. The proof has been checked in Lean, a computer verification system. The remarkable part: the original proposers of ETH, along with MIT's Ryan Williams, are now leading the public review of whether a machine has disproved their own idea.

What happens next

If the disproof holds, a large part of theoretical computer science must be revisited. Every result that says "this problem cannot be solved faster" loses its foundation. Researchers will have to determine which of those computational walls were real and which they simply stopped looking past. The new algorithm is still slow in absolute terms, and this does not solve the famous P versus NP problem, but it means the field's map of what's possible was wrong in a place where it was very confident.

If the disproof falls, ETH survives. Either way, something has shifted: an AI has produced serious, checkable work on one of the deepest questions in the discipline, serious enough that the founders of the idea had to take it seriously.