OpenAI says its AI disproved a 1999 hypothesis about how fast hard problems can be solved
OpenAI says its model found an algorithm for hard problems such as Sudoku, scheduling and the traveling salesman problem that contradicts the exponential time hypothesis (ETH) from 1999. The hypothesis held that, in the worst case, solving time doubles with each new variable, while OpenAI's algorithm grows more slowly. The proof, written in Lean, is on GitHub, and anyone can check it. For now, this is only the company's claim, and your scheduler won't get any faster.
AI-processed from TG: @hiaimedia (Hi, AI • Новости технологий); edited by Hamidun News
Imagine you're writing a shift scheduler for a warehouse or a route planner for couriers. The more orders and constraints there are, the slower the program runs, and at some point it simply can't keep up. Computer science has long asked: is this a flaw in our algorithms, or a limit of the problem itself? OpenAI says its internal model found an algorithm that refutes one of the main hypotheses on this question. For now, it is only a claim, and below we look at what is already clear about it and what isn't yet.
What the dispute is about and why Sudoku matters
The exponential time hypothesis (ETH) appeared in 1999. It concerns a large class of combinatorial problems in which a solution is easy to check but hard to find. Sudoku is a convenient example: confirming that the numbers are placed correctly takes a minute. Solving such a grid quickly is much harder, especially as it grows from 9×9 to 1000×1000. The same class includes scheduling, the traveling salesman problem and thousands of other tasks in logistics, planning and optimization.
If you try variants one by one, the maximum running time doubles with each new variable. To illustrate: if 50 conditions take an hour, 51 will take two hours and 52 will take four. There are cleverer methods that run somewhat faster. But ETH asserted that in the worst case, the time will still grow exponentially. According to OpenAI, the algorithm its model found grows slower than an exponential. That is what contradicts the hypothesis.
How it will be checked
The proof is written in Lean and published on GitHub. Lean is a formal verification system: it checks every step of the reasoning by machine, so there is no need to take the author's word for it. Anyone can run the check on their own machine. The review group will be led by MIT professor Ryan Williams and two authors of the hypothesis itself, Russell Impagliazzo and Ramamohan Paturi. In other words, the result will be assessed by the people who best understand what exactly would need to be refuted.
The caution is understandable. In early October, OpenAI published 722 papers on unsolved mathematical problems. Less than a day later, three of those papers had to be withdrawn due to an error. Some mathematicians criticized this approach. Fields Medal winner Terence Tao called the proofs that AI companies are churning out en masse in the race for benchmarks "toxic waste." Against that backdrop, the new work with a formal record looks considerably more serious, but confirmation still has to come.
What this means for practitioners
Hundreds of papers in graph theory, computational biology and databases rely on ETH. Many of them prove that certain problems cannot be solved faster than some threshold. If the refutation holds, those conclusions would lose their foundation, and theorists would have to revise part of their results.
But the effect should not be overestimated. Refuting ETH does not by itself yield fast algorithms for these problems; those would have to be found separately. So developers of schedulers, solvers and optimizers have no reason to rewrite their code today: your schedule search won't get any faster.
The story offers two practical lessons:
- When AI produces a complex result, whether a proof or code, the most important question is whether a machine can verify it. A format like Lean turns "sounds convincing" into "checked."
- Generation has become cheap, but verification remains expensive. Three papers withdrawn within a day show that the bottleneck will be the team that checks the model's conclusions, not the model itself.
If Williams, Impagliazzo and Paturi find a flaw in the proof, the story ends with another withdrawal. If they don't, AI will have refuted for the first time a hypothesis on which hundreds of works in complexity theory were built.
- Nov 21, 2026FDE job postings grew 4.6x in a year: what a forward deployed engineer actually does at the client's site
- Nov 21, 2026A swimming team captain handed ChatGPT three scheduled tasks and cut her routine work by a multiple
- Nov 21, 2026OpenAI GPT-6 Cyber Found About 35 Flaws in iPhone, Mac and Other Apple Devices
- Nov 21, 202622 Claude Agents Spent Six Weeks on Black Hole Problems — and Solved Two
Key Questions Answered
What the dispute is about and why Sudoku matters?
The exponential time hypothesis (ETH) appeared in 1999. It concerns a large class of combinatorial problems in which a solution is easy to check but hard to find. Sudoku is a convenient example: confirming that the numbers are placed correctly takes a minute. Solving such a grid quickly is much harder, especially as it grows from 9×9 to 1000×1000. The same class includes scheduling, the traveling salesman problem and thousands of other tasks in logistics, planning and optimization.
How it will be checked?
The proof is written in Lean and published on GitHub. Lean is a formal verification system: it checks every step of the reasoning by machine, so there is no need to take the author's word for it. Anyone can run the check on their own machine. The review group will be led by MIT professor Ryan Williams and two authors of the hypothesis itself, Russell Impagliazzo and Ramamohan Paturi. In other words, the result will be assessed by the people who best understand what exactly would need to be refuted.
What this means for practitioners?
Hundreds of papers in graph theory, computational biology and databases rely on ETH. Many of them prove that certain problems cannot be solved faster than some threshold. If the refutation holds, those conclusions would lose their foundation, and theorists would have to revise part of their results. But the effect should not be overestimated. Refuting ETH does not by itself yield fast algorithms for these problems; those would have to be found separately.
Test Frontier LLMs & Autonomous Agents in One Workspace
Run Claude Opus 5.5, GPT-6, Gemini 3.1, and DeepSeek side-by-side in Nomad AI (nomadnet.ai) — unified model routing, deep research, and multimodal workflows under one subscription.
The AI world, distilled — once a week
Seven stories that actually mattered, hand-picked. No noise, no reposts, no press releases.
Done! Check your inbox for a confirmation.