OpenAI says one of its internal models has disproved the Exponential Time Hypothesis, a conjecture that computer scientists have leaned on for nearly three decades to figure out how hard certain problems really are. If the result holds up, it’s a big deal, but the name alone doesn’t tell you much. Here’s what the ETH actually says, why it mattered in the first place, and what changes now that it’s been shown to be false.
The Exponential Time Hypothesis, Explained
The Exponential Time Hypothesis is a statement about a specific problem called Boolean satisfiability, or SAT for short. SAT asks a simple-sounding question: given a logical formula built out of variables that can each be true or false, connected by ANDs, ORs, and NOTs, is there some way to set those variables so the whole formula comes out true?
For a small formula, you could just try every combination. With 10 variables, that’s 1,024 possibilities, easy for a computer. The trouble is that the number of combinations doubles with every variable you add. By 100 variables, you’re looking at more combinations than there are atoms in the observable universe. SAT belongs to a famous category of problems called NP-complete, which roughly means it’s one of the hardest problems in a huge class of problems that includes scheduling, routing, circuit design, and resource allocation. Critically, all NP-complete problems are secretly the same problem in disguise: if you found a fast way to solve one of them, you could use that trick to solve all the others fast too. That’s what makes SAT special. It’s not just one hard problem, it’s a stand-in for an entire universe of hard problems.
Nobody has ever found an algorithm that solves SAT meaningfully faster than basically checking every possibility, and nobody has proven that it’s impossible either. That open question is really a cousin of computer science’s most famous unsolved problem, P vs NP, which asks whether every problem whose solution can be quickly checked can also be quickly solved. The two questions aren’t identical, but a fast algorithm for SAT would turn the computing world upside down in much the same way a proof that P equals NP would.
What the ETH actually claims
Since nobody can prove SAT is hard, researchers needed something to build on anyway. That’s where the Exponential Time Hypothesis comes in. Proposed in the late 1990s by computer scientists Russell Impagliazzo, Ramamohan Paturi, and Francis Zane, the ETH is a formal way of saying: we believe brute-force search really is close to the best you can do for SAT, and solving it will always take time that grows exponentially with the number of variables, not just somewhat slowly, but truly exponentially.
Think of it less as a proven fact and more as a reasonable, widely-shared bet, similar to how physicists work with assumptions that haven’t been fully proven but hold up against everything observed so far. Because the ETH couldn’t be proven, but seemed extremely likely to be true, researchers started using it as a foundation stone. If you assume the ETH is true, you can show that hundreds of other problems in fields like graph theory, computational biology, databases, and computational geometry must also be hard, because if any of them had a fast solution, you could use it to crack SAT faster than the ETH allows. That’s the trick computer scientists call a conditional hardness result: “problem X is hard, assuming ETH is true.” It let the field make precise, useful statements about difficulty without first needing to settle P vs NP, which has remained unsolved since it was formally posed in 1971.
Why its disproof matters
OpenAI says its model produced a natural-language disproof of the ETH, which was then checked using Lean, a proof assistant that verifies every logical step of a mathematical argument by machine rather than relying purely on human reviewers. According to the company, the result is now being independently verified by a group led by Impagliazzo and Paturi themselves, alongside MIT’s Ryan Williams, arguably the most qualified panel possible, given that two of them proposed the conjecture in the first place.
If the disproof holds, the immediate consequence is less dramatic than it might sound: SAT doesn’t suddenly become easy to solve, and P vs NP remains unresolved. What changes is the foundation underneath hundreds of existing hardness results. Papers that said “problem X cannot be solved quickly, assuming the ETH” now have their assumption pulled out from under them. That doesn’t mean those problems are suddenly easy, but it does mean the field needs to go back and work out which results still hold on different grounds, and which ones might not.
The more exciting possibility is what a disproof implies going forward. If the worst-case time needed to solve SAT is smaller than the ETH assumed, that opens the door to faster algorithms for an enormous number of real-world problems that reduce down to SAT, everything from chip verification and software testing to planning and scheduling systems. OpenAI itself is cautious here, noting that turning a theoretical refutation into a practical, faster algorithm is a substantial research problem of its own, not something that follows automatically from the proof.
There’s also a broader, less technical implication. This result arrived alongside two other AI-generated breakthroughs from OpenAI on the same day, including a proof of the Kakeya conjecture in mathematics, part of a release pattern that follows the company’s October 6 drop, a batch of results that was large enough to draw criticism from mathematicians over how such claims should be reviewed and released. The ETH case is a test of whether that review process, this time built around the conjecture’s original authors, can settle a result decisively enough for the rest of computer science to actually trust and build on it.