12 min read

AI overturns ETH

AI systems have challenged a long-held limit in computing. How much research could they carry out for themselves, and what would that mean for the rest of us?

Ben and Cai won't both come.

Guest list 1: Asha, Ben and Cai are coming. Dev is at home.

Breaks the rule: Ben and Cai are both coming.

Guest list 2: Asha, Ben and Dev are coming. Cai is at home.

Keeps the rule: Cai is at home.

Checking a list is easy. Finding one that keeps every rule gets harder as guests and rules multiply.

On 26 October, OpenAI announced that one of its AI systems had disproved the Exponential Time Hypothesis, or ETH. Anthropic followed with a separate proof, also credited to an AI model. 1 2

For more than 25 years, computer scientists used ETH to argue that certain tasks could not be solved much faster. OpenAI says hundreds of papers relied on it, in fields including graph theory, computational biology, databases and geometry. With ETH refuted, those arguments no longer establish the limits they claimed. 1

The models had produced new knowledge about a problem that had resisted researchers for decades. If AI can do that repeatedly, each discovery could help guide the next investigation.

To understand what the models achieved, start with a dinner party.

A dinner with rules

You are inviting four friends: Asha, Ben, Cai and Dev. Each one is a yes-or-no choice, and three rules apply. Can you find a guest list that keeps all three?

Build your guest list

At the party

At home

 

  1. Asha comes only if Ben comes.
  2. Ben and Cai won't both come.
  3. Someone must cook: Asha, Cai or Dev.

All 16 guest lists

 

Select a list on the board to try it.

Checking a list is easy, because you just read the rules. Finding one takes more thought, because choices interfere. Invite Cai and the cooking is solved, but then Ben stays home, and without Ben there is no Asha.

This is the puzzle behind the news. Computer scientists call it 3-SAT: many yes-or-no choices, with rules that each name at most three of them. Researchers study it closely because a great many other hard problems can be rewritten in this form. 3

Why more guests make it so much harder

Four guests give 16 possible lists. What does one more guest do to that number?

Each extra guest doubles the number of possible guest lists

 

 

  1. 16 lists with 4 guests
  2. 32 with 5
  3. 64 with 6
  4. 128 with 7
Each guest can come or stay home. These counts include all possible lists, before checking the rules.

Ten guests make 1,024 lists. Twenty make 1,048,576. Thirty make more than a billion.

Faster computers only postpone this problem. If every check costs the same, a machine 1,024 times faster has time for only ten more guests, and the next ten need the same upgrade all over again. The real hope is a better step-by-step method, or algorithm, that does not need to look at every list.

Can a clever method skip the work?

Sometimes it can. Invite Esi, Farah and Gopal to the original dinner and add three rules for them. Seven guests make 128 possible lists, and you could check them one by one. But look at who shares a rule. Asha, Ben and Cai never share one with Esi, Farah or Gopal. Only Dev appears on both sides. Settle whether Dev is coming, and the two groups stop affecting each other.

Only Dev links the two groups

Decide whether Dev comes. Then solve each group separately.

Group 1: Asha, Ben and Cai

  1. Asha comes only if Ben comes.
  2. Ben and Cai won't both come.
  3. Someone must cook: Asha, Cai or Dev.
Dev

Group 2: Esi, Farah and Gopal

  1. Esi comes only if Dev comes.
  2. Farah and Gopal won't both come.
  3. Someone must bring cake: Esi, Farah or Gopal.

Checking all 128 lists

128 checks, 24 lists work

Splitting at Dev

32 checks, 24 lists work

Each group has 8 possible lists. Check both groups with Dev coming and at home: 2 × (8 + 8) = 32 checks.

In this six-rule dinner, both methods reach 24 lists. Checking all 128 wastes effort, because it retests Asha's group for every arrangement of Esi's group, even though neither can affect the other. Splitting needs only 32 checks.

The trick depends on that clean split. Suppose Cai and Farah also won't both come. Now an option with Cai no longer fits every option from the other group, so you cannot simply multiply. Settling Cai as well as Dev restores the split, at 48 checks, and 21 lists work. Add a rule that Ben comes only if Gopal comes, and three guests must be settled first, at 64 checks, and 14 lists work. In a larger puzzle, rules can connect so many choices that no small group can be separated this way.

Over the decades, researchers developed methods that cut the work even for the most tangled puzzles. Yet the work still grew in the same basic way as puzzles got larger. 2

What experts believed

Think of savings in a bank. At a fixed interest rate, the balance grows by the same percentage every year, so it climbs faster and faster. Checking every list behaves the same way, with 100% growth per guest. Cleverer methods had lower rates, but each rate stayed fixed, however large the puzzle. This pattern is called exponential growth.

In 1999, Russell Impagliazzo and Ramamohan Paturi set out the idea that became ETH. It said the pattern could never be fully beaten. For the hardest versions of the puzzle, every possible method would keep some fixed growth rate above zero. Nobody knew how large that minimum was. ETH said only that one existed. It was never proved, but it was widely believed. 4 1

What the AI found

The new proofs describe methods that break the pattern. As puzzles get bigger, the guaranteed growth rate per guest keeps falling towards zero. Pick any fixed rate, however tiny, and for large enough puzzles the new guarantee grows more slowly than that rate would. The total work still rises. Computer scientists call this subexponential growth. 2 5

ApproachWhat happens as a guest-list puzzle grows
Checking every guest listWork doubles with every guest, a 100% rate that never changes.
Earlier better methodsWork grows at a lower rate, but still the same rate at every size.
What ETH predictedEven the best possible method keeps some fixed rate above zero.
The new guaranteeWork still rises, but the average rate per guest keeps falling towards zero.
A rate here works like interest on savings: it is the average percentage the work grows by with each added guest. The new guarantee beats each fixed rate only once puzzles are large enough.

The methods also do more than ETH required. They calculate exactly how many lists work, as you did at the dinner. A count of zero means no list works, so the count settles the yes-or-no question ETH was about. They cover every puzzle of this kind, however tangled, and they run on ordinary computers with no randomness. 2 5

The mathematics goes far beyond splitting a dinner party. One route in OpenAI's paper rewrites the puzzle as algebra, breaks the calculation into groups and keeps track of the connections through shared summaries. The dinner shows the idea they have in common: the number of possible answers does not, by itself, decide how many steps it takes to find the right one. 5

Both labs credit AI with the discovery. OpenAI says its system proved the result. Anthropic says an internal model found the core algorithm with no human input, and that its researchers then helped improve the paper. Those are the labs' own accounts of private work, but the proofs themselves are public. 1 2

Will anything run faster?

Not from this result as it stands. Anthropic calculates that, for puzzles with five rules per choice, its guarantee does not beat checking every list until a puzzle has more choices than a 1 followed by 10,000 zeros. Checking every list is already impractical at 100 choices. Anthropic says its result "says nothing about solving formulas in practice." 6

A better growth guarantee describes what happens as puzzles get larger. A practical speed-up would mean real puzzles finishing sooner. No such improvement has been shown for the tools people use today.

Can we trust it?

The evidence is strong. Both labs released proofs written for proof-checking software, which tests every logical step. People must still confirm that the checked statement says what the paper claims. Carlos Toledo reports rechecking both formal proofs, and Ryan O'Donnell has reconstructed OpenAI's argument. Russell Impagliazzo, Ramamohan Paturi and Ryan Williams are leading a wider examination, and they say their involvement is not certification. Lance Fortnow, who says he has not personally verified the proof, wrote that "it is safe to assume now that the exponential-time hypothesis is toast." 7 8 9 10 3

Software needs checks too. In 2024, a team including Jiong Yang and Mate Soos, both at NUS at the time, worked on tools that estimate how many solutions a puzzle has. The team proved the method's accuracy guarantee and supplied certificates, records that let others check each answer the tool gives. Users could check both the method's guarantee and individual results. 11

What changes for researchers

Researchers often prove that one task is hard by translating another hard problem into it. Many papers used ETH in this way. If solving a task much faster would also make the guest-list puzzle much faster to solve, ETH gave researchers a reason to rule out that improvement.

The conclusions may still be correct. They now need a justification that does not depend on ETH. 3

At NUS Computing, Divesh Aggarwal and PhD researcher Rishav Gupta studied this kind of connection with Aditya Morolia and Chuanqi Zhang. Their 2026 paper used ETH to establish limits for certain geometric problems involving regular grids of points. It showed that solving those problems much faster would also make the guest-list puzzle much faster to solve. 12

The link between the problems still holds. ETH can no longer rule out a much faster solution to the geometric problems. But the translation runs from the guest-list puzzle to those problems, so a new method for the guest-list puzzle does not automatically solve them faster. 10

Translations that run the other way can carry the new method to other tasks. Suppose you must seat guests at three tables so that rivals sit apart. Each placement is a yes-or-no question, such as "Is Asha at table 1?", so three questions per guest turn seating into the same kind of puzzle. OpenAI's paper gives a method even for counting valid seating plans, with a growth rate per guest that keeps falling as the party grows. Mathematicians call this task graph colouring. 5 13

Seat rivals at different tables

Rival pairs

  • Asha ↔ Ben
  • Ben ↔ Cai
  • Cai ↔ Dev
  • Dev ↔ Esi
  • Esi ↔ Asha

Drag guests between tables, or select one to move to the next table.

Table 1

Asha Cai

Table 2

Ben Dev Esi

Table 3

Dev and Esi clash at table 2. Move either guest.

Where is Esi sitting? Only one answer can be yes.

Table 1? No Table 2? Yes Table 3? No

5 guests × 3 questions = 15 yes-or-no choices.

30 of the 243 seating plans keep all rivals apart.

A translation also needs to keep the problem small. Seating needs only three questions per guest. Some translations add so many choices that they erase the speed advantage. Lance Fortnow names one example, the travelling salesman problem of finding the shortest tour through a list of cities. Translating it into this kind of puzzle adds too many choices, so the OpenAI method offers nothing new there. 3

What this means beyond computer science

ETH's refutation reopens questions about how much faster difficult tasks could be solved. Turning the result into useful software will require methods that work at the sizes people actually use. 1 3

A larger mathematical question remains open. P versus NP asks whether every answer that is easy to check is also easy to find. The new methods do not settle it. 2 14

The labs credit AI with finding new algorithms for a longstanding open problem. Others can examine the proofs. This is a substantial step towards AI carrying out original research with less human direction. 1 2

Imagine a system that continues after one discovery. It checks a result, identifies a worthwhile question that follows, and starts investigating it. When an attempt fails, it changes approach. A research team could use such a system to pursue promising ideas it would otherwise leave untouched for lack of time or staff.

If systems can do this reliably across science and engineering, research teams could test more ideas for better medicines and materials. Physical experiments would still take time. AI could help researchers use each result to decide which experiment to run next.

The ETH result is a milestone in AI research. The next test is whether AI can make important discoveries repeatedly, verify them and use what it learns to choose the next question.