OpenAI says its AI disproved a famous computer science rule of thumb

A hypothesis is an educated guess that nobody has proved. This one is about a puzzle called 3-SAT.

In 3-SAT you get a long list of small rules, each about three true-or-false switches. Your job is to set every switch so that all the rules are happy at once.

The hypothesis says there is no clever shortcut. Every time you add one more switch, the work needed roughly doubles.

In real life Think of a combination lock. Add one more digit and you need ten times as many tries. The hypothesis says 3-SAT behaves like a lock with no weak spot.

Why it matters: Researchers use the hypothesis as a starting assumption. If 3-SAT is truly that hard, then many other problems must be hard too.

Russell Impagliazzo and Ramamohan Paturi of UC San Diego proposed it, together with Francis Zane. It has been around for more than two decades.

Hundreds of research papers build on it. They say, in effect, "if the hypothesis holds, no fast method exists for this other problem."

OpenAI said on October 26, 2026 that an internal model found a method that beats the supposed limit. The company says the model found it on October 16.

The method is an algorithm, a step-by-step recipe a computer follows. OpenAI describes it as a deterministic one, meaning it gives the same answer every time, that counts the solutions to these puzzles in less than exponential time.

• October 16, 2026: the model finds the disproof.
• October 17, 2026: the proof is rewritten in Lean.
• October 26, 2026: OpenAI goes public and posts the proof on GitHub.

Lean is a proof checker. You write every logical step in a strict code-like language, and the program confirms each step follows from the last.

That helps with trust. A person does not have to take the AI's word for it, because the computer checks the logic line by line.

The catch: Lean checks that the proof is valid, but people still need to confirm that the statement being proved is the right one. That is part of what the human reviewers are doing.

Anthropic says yes. It posted a 49-page paper titled "A 2^o(n) Time Algorithm for 3-SAT", credited to Claude.

The company says an internal Claude research model found the core algorithm on October 16, using 14 million output tokens and no human input. A token is a small chunk of text, so that is a very long stretch of thinking.

Both labs landed on the same date. That does not prove either is right, but it makes the coincidence hard to ignore.

OpenAI asked a group of outside experts to examine its result. They are Impagliazzo and Paturi, who proposed the hypothesis, and Ryan Williams of MIT.

They work without non-disclosure agreements and without payment from OpenAI. OpenAI also gave them its raw data.

Their joint statement is careful: "If the claim is correct, it will change an important part of theoretical computer science."

Paturi added that a company's announcement cannot replace the community's judgment. Impagliazzo said he would have preferred a human to find it, someone who could explain how they thought. Williams has long doubted the hypothesis, and said he felt vindicated.

3-SAT is the root of a whole family tree. Many well-known puzzles can be turned into 3-SAT, and the hypothesis is how researchers argue they are hard too.

Anthropic's paper names a few of them:

• Independent Set: pick the biggest group of points in a network where no two are connected.
• Clique: find the biggest group where everyone is connected to everyone else.
• Vertex Cover: pick the fewest points that touch every link in a network.
• Dominating Set: pick a small group of points so that every other point sits next to one of them.

Anthropic says its result also knocks down a stronger version of the hypothesis, called the Strong Exponential Time Hypothesis. That version makes an even tighter claim about how the work grows.

Exponential growth is the doubling lock from above. Subexponential growth is slower than that, though still far from quick.

Anthropic is clear about the limits. Its paper says the new method says nothing about solving formulas in practice. The speed-up only shows up at enormous sizes, and brute force is already impractical at around 100 switches.

That is why researchers talk about this as a result about theory. It tells us where the wall really stands, not that anyone can walk through it today.

Impagliazzo has called the result "shocking news." He is one of the three people who proposed the idea, so he knows better than most how long it stood.

Reporting on the result also says it could one day speed up chip design and break some forms of encryption. That is a "someday" idea and not a claim from either lab. The experts have not yet worked out what, if anything, it means for those fields.

The catch: A company announcing a result is different from the field accepting it. Anthropic's own paper says that, at the time of writing, no person is known to have checked the formal proof.

Not yet. Disproving the hypothesis does not hand anyone a fast way to solve real puzzles.

Anthropic's paper says plainly that the result says nothing about solving formulas in practice. It also does not settle P versus NP, the best-known open question in the field.

The big picture: The surprise is not a new gadget. It is that an AI system may have found a result the field's own experts did not expect.

Until the review ends, papers that rely on the hypothesis stay as they are.

The ETH result was one of three. OpenAI also announced AI-produced proofs on two other fronts.

• Mathematics: the local smoothing and Kakeya conjectures, which describe how waves and thin shapes behave in space. A mathematician at NYU, Hong Wang, proved the three-dimensional Kakeya case in 2025.
• Physics: existence proofs for some quantum field theories, the math behind how particles interact. David Gross, a Nobel laureate, is leading a separate group that is reviewing this work.

OpenAI also put $5 million toward the Simons Foundation, to fund workshops and conferences that help researchers check and understand AI-made science.

• Nothing breaks: your apps, your passwords and your bank are not affected by this result.
• Watch the review: the outside experts will decide whether the claim stands. Treat it as promising, not final.
• Expect more of this: two labs reaching the same result on the same day suggests AI is getting useful for research math.