Is the Exponential Time Hypothesis false?

OpenAI and Anthropic each posted a proof that it is false on October 26, 2026 (US time), both with machine-checked Lean formalizations. As of October 27, 2026, neither has been peer reviewed. OpenAI says a working group led by Impagliazzo, Paturi and Ryan Williams will examine its proof.

Does this prove P = NP?

No. The claimed algorithms run in roughly 2^(n/√log n) time, which is subexponential but still slower than any polynomial. P = NP would need a polynomial-time algorithm.

How was the explainer video made?

Claude Code, an AI agent made by Anthropic, made it for Numonic. It read both papers, mapped every claim to a source line, scripted it for a synthetic voice, rendered the scenes from code, and ran three review rounds plus automated checks. Every file is kept in Numonic with its lineage.

Is the Exponential Time Hypothesis Really False?

Q: What is the Exponential Time Hypothesis?

The Exponential Time Hypothesis (ETH), proposed by Russell Impagliazzo and Ramamohan Paturi in 1999, says there is a fixed exponential rate that no algorithm for 3-SAT can beat: some constant δ > 0 such that 3-SAT on n variables cannot be solved in 2^(δn) time. It was never proven, but many results assume it.

Q: Does it break encryption or speed up SAT solvers?

Not on its own. Anthropic estimates that, for formulas with five clauses per variable, its proven bound beats brute force only beyond 10^10,000 variables, and its paper says the result says nothing about solving formulas in practice.

Status, October 27, 2026: claims under review, not peer reviewed. This post and the video were produced with Claude Code, an AI agent made by Anthropic, which is one of the two labs in this story. The video’s narration is a synthetic voice.

The short answer is maybe, with unusually strong evidence. On October 26, 2026 (US time), about six hours apart, OpenAI and Anthropic each posted a proof that the Exponential Time Hypothesis (ETH) is false. Computer scientists have built on ETH for more than 25 years. Both labs shipped machine-checked proofs, and neither proof has been peer reviewed. Until they are, treat the result as a claim, not a settled fact.

Our six-and-a-half-minute explainer is below. Claude Code, an AI agent, made it for Numonic. This post covers the result first, then how the video was made and what the checks caught. The public walk-through shows the whole run.

The explainer, 6:28. Script, scenes, and checks by Claude Code; narration by a synthetic voice (OpenAI gpt-4o-mini-tts).

What Is the Exponential Time Hypothesis?

Start with a puzzle called 3-SAT. You have a row of switches, each on or off, and a list of rules. Each rule names three switches and says at least one of them must be set a certain way. The task is to find a setting that satisfies every rule.

Checking an answer is easy. Finding one seems hard: the obvious method tries every setting, and each switch you add doubles the number of settings. Ten switches give about a thousand settings, 50 give about a quadrillion, and 100 give more than 10³⁰. That is 2ⁿ for n switches. The puzzle matters beyond itself, too. 3-SAT is NP-complete, so thousands of problems, from scheduling to chip verification, can be translated into it.

Bars for 10, 50 and 100 switches: 1,024 settings, about 1.1 quadrillion, and about 1.27 × 10^30, labeled 2 to the n — Why brute force fails: every switch doubles the settings to try.

Clever algorithms beat brute force, but only by shrinking the 2 in 2ⁿ. Before these papers, the best deterministic algorithm ran in about 1.328ⁿ time, according to both papers’ surveys of earlier work. That is still exponential: add one variable, and the work still multiplies.

In 1999, Russell Impagliazzo and Ramamohan Paturi proposed that this can never be escaped, in a conference paper whose journal version followed in 2001. The Exponential Time Hypothesis says there is some fixed exponential rate, 2^δn for some δ > 0, that no algorithm for 3-SAT can get below. It was never proven. It was assumed, and it became one of the most useful assumptions in the field. Researchers proved results of the form “if ETH is true, then this other problem cannot be solved faster than that.”

800+papers with at least one result that rests only on ETH or a hypothesis that implies it

Anthropic’s literature search

What OpenAI and Anthropic Claim

Both papers describe a deterministic algorithm for 3-SAT whose running time is subexponential. Roughly, the exponent is no longer n; it is n divided by the square root of log n. (The general bound in both papers carries an extra log log n factor, which drops for formulas with few clauses per variable.)

That divisor keeps growing, so the growth rate keeps falling, eventually below any fixed exponential you pick. That is exactly what ETH said could not happen. It is a strange middle ground: far slower than any polynomial, so this is not P = NP, but eventually faster than every exponential.

A falling growth-rate curve crossing below dashed lines for 2^0.3n, 2^0.1n and 2^0.05n, captioned “Below any fixed exponential you pick: what ETH said was impossible” — The claim in one chart. Illustrative only: constants and log log n factors omitted.

The algorithms do more than decide whether a solution exists. Both count exactly how many there are, and OpenAI’s version does it in polynomial memory.

What Breaks If the Proofs Hold

If the proofs are right, ETH is false, and so is its stronger sibling, the Strong Exponential Time Hypothesis (SETH). Variants fall too, including the gap, counting, and nondeterministic versions (Gap-ETH, #ETH, and NSETH).

Every hardness result that rested only on these hypotheses loses its foundation, but not in the same way. Some are overturned outright. Anthropic’s Corollary 7 gives algorithms for Independent Set, Clique, Vertex Cover, Dominating Set, and k-Coloring that run faster than any fixed exponential in the number of vertices, so their classic 2^Ω(n) lower bounds no longer stand. Others simply lose their reason to be believed. And some survive: lower bounds for comparing long strings, such as longest common subsequence, also follow from the Orthogonal Vectors conjecture, which neither paper claims to refute.

If the proofs hold

Result	Status
ETH and SETH	False
Gap-ETH, #ETH, NSETH	False
Clique and Independent Set 2^Ω(n) bounds	Overturned outright
Other bounds resting only on ETH or SETH	Unsupported, not disproven
Long-string bounds (e.g., LCS)	Survive through Orthogonal Vectors
P vs NP	Untouched

There are new results, too: faster exact counting of graph colorings (in both papers) and of perfect matchings (in OpenAI’s), and a new circuit lower bound in complexity theory, which both papers derive.

What It Does Not Do

It does not prove P = NP. These algorithms are still slower than any polynomial. And, on its own, it does not break today’s encryption.

Nor does it speed up every NP problem. OpenAI’s paper notes that a subexponential bound does not survive general polynomial-time translations between problems, though the speedup does carry over to some, such as the graph problems above.

It will not speed up real SAT solvers either. For a formula with five clauses per variable, Anthropic estimates its proven bound beats brute force only beyond 10^10,000 variables. The observable universe holds about 10⁸⁰ atoms. Anthropic’s own summary is that the result “says nothing about solving formulas in practice.” This is a result about the shape of computation, not about tomorrow’s software.

10^10,000variables before Anthropic’s proven bound beats brute force, for formulas with five clauses per variable

Is the Proof Correct?

Both labs shipped machine-checked proofs in Lean, a proof assistant that verifies every logical step. That is strong evidence. But Lean checks a proof of a formal statement, and people still have to confirm that the statement says what the paper claims. Anthropic’s repository puts it plainly: “Lean checks the proofs, but no machine checks that this file says what the paper says.”

The gaps are documented. OpenAI’s Lean proof gives a weaker bound than its paper’s sharpest one, though still subexponential. Anthropic’s paper lists where its Lean statements differ from the printed ones.

Neither result has been peer reviewed. OpenAI says an independent working group led by Impagliazzo, Paturi, and Ryan Williams will examine and explain its proof. Two of them proposed ETH in the first place. Until they report, treat this as a claim with unusually strong evidence, not a settled fact.

Who Proved It?

Neither paper lists a human author. OpenAI credits an unnamed internal model, which was posed about 4,000 research problems; its public collection holds 721 manuscripts at different stages of verification. Anthropic says its core algorithm was found on October 16 by an internal Claude research model, using 14 million output tokens and no human input, and that its researchers then helped Claude write up the paper. OpenAI’s manuscript is dated October 17 and revised October 25; it gives no discovery date.

Timeline from October 16, when Anthropic says its core algorithm was found, through October 17 and 25 for OpenAI’s manuscript dates, to October 26, when both were posted — Who proved it: each lab's own dates, from October 16 to the postings on October 26.

Anthropic describes the two results as independent and concurrent. If they hold, two AI systems, by the labs’ own accounts working independently, reached the same result within days of each other. The biggest story may not be what was proven, but what proved it.

How an AI Agent Made This Explainer With Numonic

One request started it: make the best possible explainer of what the result would mean if it is true, review it in rounds with our media checks, file everything in Numonic, and come back only when it is ready for YouTube. Claude Code did the rest in about four hours: sources, script, synthetic narration, motion graphics rendered from code, three rounds of review, and filing. There is no music and there are no burned-in subtitles, by house rule.

That comes with a conflict of interest. Claude Code is made by Anthropic, one of the two labs in the story, so lab balance was a checked item rather than an intention. The first fact-check flagged four lines whose wording tilted toward one lab or the other, and they were rewritten.

How the Agent Made and Checked the Video

Read

Both preprints and both repositories, first

Map

Every spoken claim tied to a source line

Fact-check

A separate agent checks all 43 lines

Review

Three rounds on frames, timing, and claims

Gate and file

Tool checks, then every file into Numonic

Sources before script

12 of 43narration lines changed by the first fact-check31 passed, none cut

The agent read both preprints and both repositories before writing a word. Every spoken claim then went into a claim matrix, a table that ties each claim to the line in a primary source that supports it, or marks it as general knowledge. A separate review agent checked all 43 narration lines against those sources.

The changes were small, and they mattered. “Published” became “posted,” because neither paper is peer reviewed. Finding a solution became something that “seems hard,” because the sources do not say it is proven hard. The 800-paper figure gained the word “only,” which Anthropic’s count depends on. Later rounds moved ETH’s origin from the 2001 journal paper to the 1999 conference paper, and added that Corollary 7 overturns some lower bounds outright.

Three review rounds, and what they caught

In each round, review agents separate from the maker read frame sheets of every chapter, frame strips around every page change, the scene source code, and the primary sources. Round 1 found four defects a viewer would notice, plus about 37 corrections to on-screen text and packaging. Round 2 found no new visible defects and five corrections. Round 3 found none, and one correction that turned out to be the most interesting catch of the run. Each pair below shows the first render, then the final.

First render: the “unusually strong evidence” label wraps onto the meter bar, and the cards date ETH to 2001 — The label wrapped onto the meter bar and the marker hung below the track. The same frame dated ETH to 2001; the final says 1999.

Final render: the label sits on one line above the bar, the marker crosses it, and the cards date ETH to 1999 — The label wrapped onto the meter bar and the marker hung below the track. The same frame dated ETH to 2001; the final says 1999.

First render: the 1.3 to the n curve rises, then runs flat along the top of the chart — The narration says the work multiplies forever, but the first curve ran flat along the top of the chart. The final curve leaves it.

Final render: the curve leaves the top of the chart, marked “off the chart” — The narration says the work multiplies forever, but the first curve ran flat along the top of the chart. The final curve leaves it.

First render: an almost empty frame with only a small “Real SAT solvers” tag — For 6.6 seconds only a small tag was on screen while the voice explained why SAT solvers will not get faster. The final shows the point from the first word.

Final render: the headline “Faster SAT solvers? No.” — For 6.6 seconds only a small tag was on screen while the voice explained why SAT solvers will not get faster. The final shows the point from the first word.

First render: a list of hypotheses and the next page’s red ETH and SETH bar overlap mid-transition — During a page change, the next page faded in on top of the old one for about 10 frames. Pages now change in sequence.

Final render: the same moment shows only the new page — During a page change, the next page faded in on top of the old one for about 10 frames. Pages now change in sequence.

First render: three lower-bound cards, all labeled “unsupported, not disproven” — All three bounds on the page were labeled “unsupported, not disproven,” but Anthropic’s Corollary 7 overturns the Clique and Independent Set bounds outright. The final says so.

Final render: the Clique and Independent Set card is labeled “overturned outright”; the others “unsupported, not disproven” — All three bounds on the page were labeled “unsupported, not disproven,” but Anthropic’s Corollary 7 overturns the Clique and Independent Set bounds outright. The final says so.

The reviewers were Claude agents, too, so they were not independent of the maker, and the run’s own QC report treats their verdicts as weak signals. The checks that were independent of the maker were tools: speech recognition, loudness measurement, a contrast and reading-time check, and a layout probe.

The catch the eyes missed: a dropped sentence

The text-to-speech voice silently dropped the last sentence of one line. Line 9 ends “That’s two to the n,” and the voice left it out in two of four takes. Every take went through a speech-recognition model that is independent of the voice, and that check flagged the line. But line 9 is full of numbers, and the flag was read as a number-formatting difference, so the gap went unnoticed until round 3.

Round 3 caught it by comparing the captions with the audio: the caption read “That’s 2ⁿ,” and the master was silent at that moment. The line was voiced again, and every take now gets a word-by-word comparison with the script, with digits spelled out. A synthetic voice can drop a whole sentence and still sound fine, and an automated check helps only if its flag is read correctly.

The gates the final master passed

Loudness of −14.1 LUFS and a true peak of −1.4 dBTP, at 1920×1080 and 6:28.
A HyperFrames check with no errors: all 42 text samples pass WCAG AA contrast, and every line stays on screen long enough to read (29 reading-time warnings at the start, none at the end).
A layout probe sampling 10 times a second: no clipped text, and nothing under 16 pixels at 1080p.
Speech recognition of the whole master: every line present, with a 4.8 percent word error rate traced to names, digits, and other quirks of the recognizer.
Provenance: the master carries a lineage record that Numonic reads back (the scene render, the brand outro, and all 43 narration takes) and an IPTC AI-disclosure tag.

The QC report also lists what no tool could judge and a person should: a listen to the hardest names, a judgment of whether the pacing holds attention, and a theorist’s read of the section on what breaks and what survives.

Every Source, Take, and Check, Kept With Its Lineage

Nothing from the run was thrown away. The private Numonic workspace holds 78 assets in seven folders: 7 sources, 4 script and claim files, 47 voice files (two of them superseded), 3 renders, 9 QC files, 6 packaging files, and the final master with its captions. The master’s lineage ties it to the scene render, the brand outro, and all 43 narration takes.

From the video's last chapter: its collection tree in Numonic and the master's lineage.

That matters most when the verdict arrives. When the working group reports, the claim matrix points to the exact lines to voice again and the scenes to render again, and the versions they replace stay on record beside them. The public walk-through shows the run stage by stage: the video, the review pairs above, QC sheets, thumbnails, and a note at each stage on what was kept or changed.

Key Takeaways

If the proofs hold, ETH and SETH are false: 3-SAT can be solved faster than any fixed exponential, though still far slower than any polynomial.
Some lower bounds fall outright, others lose their support, and some, such as those that also follow from Orthogonal Vectors, survive.
It is not P = NP, it does not by itself break encryption, and its proven bound beats brute force only at sizes far beyond the number of atoms in the universe.
As of October 27, 2026, both results are claims with machine-checked proofs, not yet peer reviewed.
When an agent makes an explainer, have it read the sources first, map every claim to a source line, and diff every synthetic voice take against the script.
Keep every source, take, and check with its lineage. When the facts change, you know exactly what to fix.

Primary Sources

OpenAI, “The Exponential Time Hypothesis is False” (preprint, October 2026), its Lean formalization scope, and the release notes announcing the working group.
Claude (Anthropic), “A 2^o(n) Time Algorithm for 3-SAT”, with its Lean proof.
Russell Impagliazzo and Ramamohan Paturi, “Complexity of k-SAT”, IEEE Conference on Computational Complexity, 1999 (journal version 2001).