← Richard Brooks

Essay · October 2026

Two machines broke the same rule on the same day

On Friday 16 October, somewhere inside OpenAI, a machine broke a rule that computer scientists had trusted for 27 years. On the same day, somewhere inside Anthropic, a different machine broke the same rule. Neither knew about the other.

We only found out this week. OpenAI announced its result on Monday. Hours later, Anthropic published its own, with a different method and the same date. I spent a late night in Edinburgh trying to understand what had happened, asking more questions than I’d like to admit. Here they are, with the answers I wish someone had given me at the start.

What rule did they break?

It’s called the Exponential Time Hypothesis, or ETH, and it’s about a puzzle called 3-SAT.

3-SAT is a giant logic puzzle. You have a long list of conditions, each involving three switches that can be on or off, and you need to find a setting of every switch that satisfies all of them at once. Add a switch and the number of possible settings doubles. With 300 switches there are more combinations than atoms in the universe.

Figure 1

Every switch doubles the work

16,777,216combinations to check with 24 switches
Each new switch doubles the possible settings. Ten switches give 1,024 combinations, twenty give over a million, and 300 give more than there are atoms in the observable universe.

In 1999, Russell Impagliazzo and Ramamohan Paturi at UC San Diego, later joined by Francis Zane, put a name to what everyone suspected. ETH says there is no clever shortcut for this kind of puzzle. As it grows, the time to solve it grows exponentially, and no algorithm will ever change that.

Nobody ever proved it, but hundreds of research papers were built on the assumption that it was true.

So what did the machines find?

A shortcut. A modest one, much smaller than some posts have claimed, but any genuine shortcut is enough to kill the rule.

OpenAI’s paper, The Exponential Time Hypothesis is False, gives a method that counts every solution to these puzzles in what mathematicians call subexponential time. Its unreleased internal model produced the argument on 16 October and a machine-checked version the next day. OpenAI then handed it to a working group led by Impagliazzo and Paturi themselves, alongside MIT’s Ryan Williams. How must it feel to see your own hypothesis overturned, then be asked to check the proof?

Anthropic’s paper, A 2^o(n) Time Algorithm for 3-SAT, is credited simply to “Claude (Anthropic)”. Its internal research model found the core algorithm on the same day, using 14 million output tokens and no human input. The route is different, built on a technique for contracting what are called tensor networks. Both labs say plainly that the speed-up is theoretical and changes nothing about solving puzzles in practice.

Both proofs come with a version written in Lean, a programming language that checks every logical step of a proof the way a spellchecker checks words, except it doesn’t miss anything.

Does this mean P = NP?

No. This is the mistake I’ve seen most often online this week, including from people who should know better.

P vs NP is the most famous open question in computer science, with a $1 million prize attached. P is the set of problems computers can solve quickly. NP is the set of problems where a proposed answer can be checked quickly, like a finished Sudoku grid. The question is whether every quick-to-check problem is secretly quick to solve. If it were, most of today’s encryption would collapse.

It helps to think of three speeds. Polynomial is fast, the world of P. Exponential is hopelessly slow as puzzles grow. Subexponential sits in between. ETH said 3-SAT was stuck at the slow end. The new result moves it just into the middle. P = NP would need it to reach the fast end, and nothing here gets close.

Figure 2

Three speeds, and where 3-SAT moved

Steps needed as the puzzle grows, on a log scale. ETH said 3-SAT sat on the top curve. The 2026 results put it on the middle one, only a little below exponential. P = NP would need the bottom curve. The curves show the shape of each growth rate, not exact running times.

One popular post on X this week claimed the result means either P = NP or hard problems sit somewhere in the middle. That’s a false choice. Hard problems can sit in the middle zone while P and NP stay different, which is what most experts still expect. The same post suggested the new speed might be close to fast. It isn’t. The actual improvement sits just inside the middle zone, right at the slow edge.

How can you prove something wrong without knowing what’s right?

This was the question that kept me up. It turns out proving a claim wrong is far easier than finding the whole truth.

For years, people said no human could run a mile in under four minutes. On 6 May 1954, Roger Bannister ran it in 3:59.4 at Iffley Road in Oxford. One run, and the claim was dead. But that run told nobody what the fastest possible mile would be. Seventy years on, we still don’t know.

Figure 3

One run killed the four-minute barrier

Mile world records, 1942 to 1999. Bannister's run proved the barrier false. It said nothing about where the real limit lies. ETH fell the same way.

ETH works the same way. The claim was “nothing beats exponential time”. The machines produced a method that does, so the claim is false. What the fastest possible method might be remains wide open. This modest speed-up could be the limit, or far faster methods could be waiting to be found.

And we do know why the method works, in one sense. The papers lay it out step by step, and Lean has confirmed every step. What humans don’t yet have is an intuitive feel for it. It’s a bit like being handed an engine, confirming it runs, and then needing months of engineering to understand why the design is so good. That’s the job the expert groups now face.

Why does it matter that there are two proofs?

This is the part that excites me most.

AI-generated maths has had a rocky month. On 6 October OpenAI released 722 manuscripts in one go, and within a day it withdrew three of them after a sign error was found. More than a thousand mathematicians signed an open letter calling the approach research misconduct, and a group of them called for a boycott. A healthy dose of scepticism was justified.

One lab announcing a stunning result could be a mistake, or hype. Two rival labs, using different methods, reaching the same conclusion on the same day, with both proofs checked line by line by a machine, is a different matter. In science, independent replication is the gold standard. We rarely get it this fast, and we almost never get it from competitors.

Figure 4

Two labs, one date

October 2026. Both labs date the discovery to Friday 16 October, by different methods, each later checked line by line in Lean.

The shared date will raise eyebrows, and I’d expect questions about it. My guess is simpler. ETH had become a known target, and the frontier models from both labs crossed the same capability line in the same week. That says something on its own. This wasn’t one company with a magic model. It looks like the whole frontier moved at once.

What actually changes?

In the short term, almost nothing you’d notice. No encryption breaks. No app gets faster tomorrow. Ethereum is fine too, despite a few panicked posts confusing the Exponential Time Hypothesis with the cryptocurrency that shares its initials.

For computer science, a lot. Hundreds of papers proved results of the form “if ETH is true, then this problem is hard”. Every one of them now needs rechecking. A guess that held up a whole wing of the building has been pulled out, and nobody yet knows which rooms are still standing.

For the rest of us, the bigger shift is in who does the discovering. Until now, AI has been brilliant at recombining what humans already knew. This is knowledge that didn’t exist, on a problem experts had failed at for decades. People still choose which problems matter, check the work and explain what it means. But for the first time, a machine found the answer before any human did, and the humans are catching up.

I work with business leaders who still tell me AI can’t do genuinely original, expert work. After this week, I don’t think that’s a safe assumption for anyone. The open question for me is the uncomfortable one. Both breakthroughs came from internal models the public can’t use, which leaves a handful of companies holding research capability ahead of our universities.

So what’s our challenge now?

Delegation. AI is now doing research, and the hard part has moved from doing the work to handing it over well.

What did the humans actually do in both labs? They chose ETH as a problem worth attacking. They let the model run, 14 million tokens of it in Anthropic’s case. Then they checked the answer with Lean and handed it to the world’s leading experts to scrutinise. That’s delegation in its purest form: choosing the right job, briefing it clearly, letting go and verifying what comes back.

Figure 5

The delegation loop

  1. ChooseA problem worth the effort. Both labs picked ETH.
  2. BriefThe outcome stated clearly, without prescribing the route.
  3. Let goThe work runs. Anthropic's model used 14 million tokens with no human input.
  4. VerifyWhat comes back gets checked. Lean, then the experts who proposed ETH.
The work transfers. The accountability never does.

Anyone who has managed people knows how hard that is. Most of us delegate badly. We hand over tasks instead of outcomes, we hover, or we accept the result without checking it. The same failings will show up with AI, only faster and at greater scale. OpenAI’s three withdrawn papers are a reminder of what happens when the checking falls behind the output.

So the questions I’m now asking clients have changed. Which problems are worth giving to AI? How do we brief it so it attacks the right one? And what is our equivalent of Lean, the check that tells us whether to trust what comes back? The accountability never transfers. Only the work does.

Where does that leave us?

Russell Impagliazzo is the person I’d most like to have a drink with this week. In 1999 he wrote down a hunch about how hard certain puzzles must be. A generation of researchers built on it. This month, two machines in two rival companies quietly showed it was wrong, and now he’s one of the people reading their work, line by line, to understand how.

Good scientists have always followed the evidence when it moves, even when it moves against them. The difference now is that the evidence is being produced by something that isn’t us, and it’s moving faster than we can read.

Sources

Richard Brooks writes on business, value, and value AI actually delivers. He is the author of AI Strategy for Sales Teams. For work, there is my company. This essay is also available as markdown.