The Exponential Time Hypothesis, and OpenAI’s claim to break it

The problem

Every extra switch doubles the work

Picture a wall of light switches, each either on or off, and a list of rules about which ones should be on. You want a setting that obeys every rule.

The obvious way is to try every setting. One switch has 2 settings, two switches have 4, three have 8. Each new switch doubles the list. With 300 switches the number of settings has 91 digits, more than the number of atoms in the observable universe (about 10⁸⁰).

The puzzle

Rules that each mention three switches

In our puzzle every rule names three switches and is happy if at least one of them is the way it wants. “Not-b” means the rule wants b off. Below, three switches and two rules: six of the eight settings keep both rules happy.

Computer scientists call this puzzle 3-SAT (“SAT” as in “satisfy the rules”). The switches are called variables and the rules clauses. Rule 1 here is the example used in OpenAI’s paper.

Why this puzzle

Many other problems hide inside it

Many real problems can be rewritten as switches and rules: filling a Sudoku, building an exam timetable with no clashes, checking that a computer chip has no design bug. Each choice becomes a switch; each requirement becomes a rule.

That makes 3-SAT a master puzzle. A truly fast way to solve it would give a truly fast way to solve all of them, so its true difficulty is one of the central questions in computer science.

Fast vs slow

Two kinds of growth, worlds apart

Computer scientists sort methods by how their work grows with the size, n. “Truly fast” methods grow like a fixed power of n, such as n×n×n (written n³) or even n¹⁰: double the switches and n³ gives eight times the work. Doubling methods grow like 2ⁿ: add one switch, double the work.

At 100 switches, on a computer doing a billion steps per second, the gap is a thousandth of a second (for n³) against 40 trillion years, about 3,000 times the age of the universe.

What people tried

Clever tricks shrink the doubling, not the growth

Nobody has found a truly fast method. The best tricks skip most settings: a 1999 method multiplies work by 4/3 per extra switch instead of 2, and later work got this to about 1.308 (figures as listed in OpenAI’s paper).

That is a huge saving: at 100 switches the 1.308 method takes about 8 minutes at a billion steps a second. But at 200 switches it takes 6.6 million years. Each bar below shows the number of digits in the step count; doubling the switches doubles the digits, which means the actual work gets squared.

The hypothesis

ETH: the multiplier can’t sink toward ×1

In 2001, Russell Impagliazzo and Ramamohan Paturi, with Francis Zane in a companion paper, wrote down a bet called the Exponential Time Hypothesis (ETH). Picture the extra work each added switch causes as a multiplier: ×2 for checking everything, ×1.308 for the best trick.

ETH says that however clever the method, this multiplier for 3-SAT stays above some floor that is bigger than ×1. Work can never stop growing at a steady percentage per switch. Nobody proved it; nearly everyone believed it.

Why it mattered

Hundreds of results were built on it

Proving that a problem cannot be solved faster is extremely hard. So researchers proved something easier: “if this problem could be solved much faster, then 3-SAT could be too, and ETH would be false.” Believing ETH meant believing the speed limit.

OpenAI says hundreds of papers in fields such as databases, biology and geometry rest on ETH or its stronger version (strong ETH). Anthropic’s paper reports that a search by its AI found more than 800. Some of these results can also be proved from other, separate guesses, which still stand.

The claim

OpenAI’s method: the multiplier slowly shrinks

OpenAI’s paper describes a method whose work, for any puzzle, grows like 2 to the power n × (ln ln n) ÷ √(ln n), times a much smaller extra factor. Here ln is the natural logarithm, which grows very slowly: ln of a million is about 14. When each switch appears in only a few rules, the formula gets simpler: 2 to the power n ÷ √(ln n).

Either way, the extra work per switch eventually slides toward ×1 and under any floor you pick, which is exactly what ETH ruled out. But look how late: in general it only beats the best earlier ×1.308 at around 10⁷⁸ switches, close to the number of atoms in the universe. Before that it is worse.

The method has real strengths: it is exact (it counts every solution, not just finds one), involves no luck, needs little memory, and works for rules of any fixed length, not only three.

In numbers

At a million switches, the formula matters

A worked example with the unknown factor c set to 1. Checking every setting of a million switches takes 2 to the power 1,000,000 steps. The few-rules formula divides that exponent by √(ln 1,000,000) ≈ 3.72, leaving 2 to the power 269,000.

The general formula leaves about 706,000. The version Lean actually checked uses an even looser formula, which at this size is worse than checking everything: about 1,855,000. All of them prove the same point about growth in the very long run.

Try it

When does the new method actually win?

Pick which formula to believe: the few-rules one, the general one from the paper’s main theorem, or the looser one Lean checked. The paper’s formulas also hide a fixed factor c, so c is a slider: c = 1 is a friendly guess. Bars count steps as powers of ten. The dashed line is what a billion billion steps a second since the Big Bang would buy.

Move the switches slider and watch whether the orange bar ever gets shorter than the teal one.

With the general formula and c = 1, the claimed method beats the best earlier one only beyond about 10⁷⁸ switches. Anthropic’s paper is just as blunt about its own version: it “says nothing about solving formulas in practice.” A result can be important for theory and useless for real puzzles.

The common mistake

Better than doubling is not fast

The new method is “sub-exponential”: in the long run it grows slower than any steady doubling, but much faster than n³ or any fixed power. At 1,000 switches even its friendliest formula only matches the best earlier method; the general one is far slower.

So it does not settle the famous P vs NP question, the million-dollar prize asking whether every puzzle whose answers are quick to check is also quick to solve. ETH was the bolder bet: if ETH were true, “P is not NP” would follow automatically. That is why ETH can fall while P vs NP stays open.

A second lab

Anthropic’s AI reached the same claim

On the same day as OpenAI’s announcement, Anthropic released a paper credited to “Claude, Anthropic”, claiming a no-luck method that counts 3-SAT solutions with sub-exponential work. It says its AI found the core method on 16 October, with no human input, and that the result is formalised in Lean.

Its general formula has the same shape as OpenAI’s, and it says OpenAI’s work was done “independently and concurrently”. Two labs reaching the same claim separately is encouraging, but neither paper has been through expert review yet.

Where it stands

Claimed, computer-checked, not yet accepted

OpenAI checked the proof with Lean, a program that verifies every logical step of a proof, like a strict spell-checker for maths. The exact statement it checked, written in Lean’s own precise language, is public.

Lean only confirms that the proof proves that statement. People must still confirm the statement really means “ETH is false”. This worry is real: with OpenAI’s earlier Navier–Stokes result, readers worried Lean had checked a weaker statement than the one announced.

Ryan Williams (MIT), Impagliazzo and Paturi are organising an open check, with no secrecy agreements and no pay. Their open letter is clear: “Our involvement should not be taken as certification of the claim.”

An error in how the Lean statement defines the machine, the input or the running time would let a correct Lean proof prove the wrong thing. That gap is why the human review matters.

So what

If it survives review