🎯 Two labs, one date 0:00
The Exponential Time Hypothesis — ETH to the people who study it — is a bet computer scientists have leaned on since 1999. The video opens with the version of the story the headlines ran: on 16 October 2026 a model inside OpenAI worked out that the bet was wrong. On the very same day, a model inside Anthropic worked out the same thing, with no human help. Both companies published within hours of each other, and both say ETH is false, not merely shaky.
The OpenAI paper got the traffic — "ETH OpenAI" trended overnight — but almost every story left out the second lab, and the most important word in the whole affair, which is "claim". That framing is the most useful thing this video does: it is a six-minute correction to a news cycle that had already decided a 27-year-old conjecture was dead.
🔦 The bet: 100 light switches and 1999 0:46
The video's explanation is the one to keep, because it is more accurate than most of the coverage. Picture a hundred light switches and a list of rules, each saying that at least one of three specified switches must be set a particular way. If someone hands you a setting, checking it against the rules takes a moment. Finding one yourself, as far as anyone knew, means grinding through possibilities — and a hundred switches give you about 2100 ≈ 1030 settings, which the narrator calls "a million trillion trillion".
That puzzle is 3-SAT, the standard hard problem of computer science: it was the first problem proved NP-complete, and every NP problem can be encoded into it. In 1999 Russell Impagliazzo and Ramamohan Paturi (with Francis Zane, in the joint paper that supplies the technical machinery) wrote down a bet: you can shave that pile down, but it stays exponential forever, so no clever trick fully escapes it. Formally, 3-SAT on n variables requires 2Ω(n) time in the worst case.
The bet survived a quarter century of attacks. The best algorithms shaved 2n down to roughly 1.328n (deterministic, Liu 2018) and 1.308n (randomized, the PPSZ line of work) — which is the "1.3 to the power of a hundred" the video quotes. Progress from 2.0 to 1.3 over decades looked exactly like what a true conjecture should look like: constant-factor grinding, never a change of regime.
🧨 Why ETH carries 800 papers 1:34
ETH is not interesting because of 3-SAT. It is interesting because researchers built on it: you assume ETH, and out drops a hardness result for graph problems, computational biology, databases, string matching, and most of fine-grained complexity. The video's kill-shot statistic comes straight out of Anthropic's paper: a literature search carried out by Claude found more than 800 papers that prove at least one result of their own only under ETH, or under a hypothesis that implies it such as SETH or Gap-ETH. Papers that also rest on a hypothesis nobody has refuted (Orthogonal Vectors) were deliberately not counted.
The human detail worth keeping is Ryan Williams' 2019 estimate that ETH was about 70% likely to be true — "roughly how sure I am about a weather forecast", as the narrator puts it. Thirty percent doubt is a lot to carry on a foundation. The rejoinder is that a 70% belief still justifies a literature: you can build on a likely assumption as long as everyone knows it is an assumption.
| Hypothesis | What it claims | Status after these two papers |
|---|---|---|
| P ≠ NP | 3-SAT is not solvable in polynomial time | Untouched. The new algorithms are subexponential, not polynomial. |
| ETH | 3-SAT needs 2Ω(n) time | Refuted on paper: a deterministic 2o(n) algorithm exists. |
| SETH | k-SAT needs ~2n time for large k | Also refuted (Corollary 5 of Anthropic's paper), since SETH implies ETH. |
| Orthogonal Vectors (OV) | A SETH-implied assumption behind many fine-grained lower bounds | Survives. Neither paper touches it — the part of the foundation that still stands. |
📄 OpenAI's paper: count every setting, don't search 2:01
OpenAI posted first, in the public openai/math repository — a folder of 721 model-written manuscripts in 373 families, roughly 42% of whose top-line results carry Lean formalisations. The ETH manuscript's title does not hedge at all: The Exponential Time Hypothesis is False. It gives a deterministic algorithm that exactly counts the satisfying assignments of a k-CNF formula in polynomial space and time
(n + m)Ok(1) · 2n/(log n)1+o(1)
which grows more slowly than any exponential in n. Counting, not deciding, is the harder job; deciding satisfiability is then the question "is the count above zero?". The paper is dated 17 October 2026 and revised 25 October; OpenAI says the model found the result on 16 October and that the Lean proof checker accepted the formalisation the next day. Appendix C carries the part the headlines never mention: quantitative consequences, including circuit lower bounds, and subexponential algorithms for inverting Boolean maps with constant output locality.
🅰️ Anthropic's paper: same wall, a different road 2:28
That evening, Anthropic posted its own paper with the author given simply as "Claude". Its provenance note is the most quotable paragraph of the week: the core algorithm was found on 16 October by an internal Claude research model using 14 million output tokens and no human input; Anthropic researchers then worked with Claude to improve the presentation. It reaches the same conclusion by a different road — tensor networks and rank bounds rather than shared linear summaries — and it refutes SETH as well, but explicitly leaves the Orthogonal Vectors hypothesis standing.
The two papers are worth comparing side by side, because "the same result" hides two genuinely different proofs:
| OpenAI — "The Exponential Time Hypothesis is False" | Anthropic — "A 2o(n) Time Algorithm for 3-SAT" | |
|---|---|---|
| Author of record | OpenAI | Claude (Anthropic) |
| Date in paper | 17 October 2026, revised 25 October 2026 | 26 October 2026 |
| Time bound | (n+m)Ok(1) · 2n/(log n)1+o(1) | 2O(min{k√(n log log n / log n), km/√log m}) |
| Space | Polynomial | Polynomial (as stated) |
| Technique | Shared linear summaries, low-degree replacement forms, counting common zeros | Tensor-network contraction, rank bounds, grid swaps |
| Provenance of the idea | Internal model, same evaluation pipeline as the other 720 manuscripts | Internal Claude model, 14M output tokens, no human input |
| Formalisation | Lean, in the repo's shared library | Lean 4.33.1, 1,050 modules, in eth/ |
| Also refutes SETH? | Yes (refuting ETH implies SETH) | Yes — stated as Corollary 5 |
| Distances itself from OV? | ETH-based results only | Explicitly: OV-based lower bounds survive |
Anthropic's paper even mentions its rival in one quiet sentence — "an internal model at OpenAI claims to have proven a similar result" — which is the politest simultaneous-discovery note in recent memory. The video's read is fair: two rivals colliding, in public, with citations.
⚠️ What the headlines got wrong: "OpenAI" and "disproved" 3:03
Two words in "OpenAI disproved the Exponential Time Hypothesis" are shaky. "OpenAI", because a second lab reached the same result on the same date and nobody outside either company can check who got there first — the timestamps live in internal logs. "Disproved", because a refutation is only as good as the checking, and the checking has barely begun.
OpenAI asked three people to examine the proof: Impagliazzo and Paturi, the two who proposed the hypothesis, and Ryan Williams at MIT. Their open letter to the field says, in as many words, that their involvement should not be taken as certification of the claim, and that a result of this significance requires careful, independent scrutiny.
Williams added on X that the group signed no non-disclosure agreements and is not being paid. The checkers asked OpenAI to release all its raw data and to fund a conference so the community could work through the proof; OpenAI agreed to both, and separately put $5 million into the Simons Foundation for workshops and conferences on AI-produced results. The video closes on exactly this: the hard part is no longer finding a proof, it is finding people with the time to read one.
🔍 What Lean actually checks 3:40
The proof checker is the easiest part of this story to oversell, and the video gets the distinction exactly right. Lean confirms that every step of the formal proof follows from the previous one, and both proofs pass. What no machine can confirm is that the statement at the top says what the paper says it does — the specification problem. Both labs say so in writing, which is more than most press releases manage.
Anthropic's README is unusually explicit about how far the checking goes: MainResults.lean is one commented file that states what is proved, and it contains no proofs. Lean checks the proofs; no machine checks that this file says what the paper says, so the file is deliberately kept short enough for a human to read. The development uses Lean v4.33.1 over Mathlib at commit 0df444a…, rests on no axioms beyond Lean's three standard ones (propext, Classical.choice, Quot.sound), and is accepted by Lean's kernel, by leanchecker module by module, and — through Comparator — by an independently implemented kernel, nanoda.
| What is machine-checked | What is not |
|---|---|
| Every proof step follows from the previous one (Lean kernel) | That ETHIsFalse means what a complexity theorist means by "ETH is false" |
| The development builds from nothing; all 1,050 modules compiled together | The value of the constant in the time bound — Anthropic notes it is not explicit |
| No axioms beyond the three standard ones; a second kernel (nanoda) re-checks via Comparator | Whether the reduction from the paper's prose to the formal statement has a gap |
| An earlier token-identical copy re-checked from an empty environment, Mathlib included | Who — if anyone — has read the whole listing end to end |
🤖 The proof nobody has read 3:57
Anthropic goes further than OpenAI on one point, and it is the sentence the video cannot stop thinking about. Its Lean proof — over a thousand files — was written by AI models and reviewed by other instances of the same models, and at the time of writing no person is known to have checked it. That is stated in the paper, not extracted from it.
Read carefully, this is three claims stacked on each other: the mathematical argument was found by a model; the formalisation of that argument was written by models; and the review of the formalisation was carried out by models reviewing models. The kernel makes the middle layer unusually trustworthy — a machine-checked proof cannot be subtly wrong in the way prose can. But the layer above and below it (is the statement faithful? is the paper's theorem the Lean theorem?) remains a human job that, so far, has no named human attached.
The video's verdict — "more honest than any press release I've read this year, and slightly terrifying" — is the right tone. Anthropic also published a condensed description of the key idea, which it says Claude Opus 5.5 at high effort can use to rederive the refutation. That is a deliberate, and remarkable, editorial choice: releasing the seed of the proof alongside the proof.
📉 Faster, but not for anyone alive 4:18
The strangest part of the story is the one Anthropic is admirably blunt about: the method only beats plain brute force on formulas with more than 1010,000 variables — a one followed by ten thousand zeros. For scale, there are about 1080 atoms in the observable universe. For any puzzle that fits inside reality, trying every setting is still quicker.
The paper is more precise than the video: for 3-CNF formulas with m = 5n clauses, the proven bound does not improve on 2n unless n > 1010,000; the bound in n alone does not improve unless n > 1010; and the authors say the general approach "seems unlikely to yield any general improvement unless n > 107", while brute force is already impractical at n = 100. Then the sentence that should be printed on every headline: "Thus our result says nothing about solving formulas in practice."
Lance Fortnow, a complexity theorist, told reporters the approach looks promising but expects little effect on real-world puzzle-solving software. So: it will not crack your passwords, it will not make your satnav faster, and it will not change a single line of production code this year. Anyone selling you a practical speed-up from this result is selling you something else.
🗺️ What actually changes: the map, not the machine 5:01
If it holds, hundreds of results that say "you cannot do better than this, unless ETH is false" lose the ground they stand on, and some will need new proofs — or will quietly become true-but-unconditional, since the refutation of ETH gives new algorithmic tools rather than taking them away. The most concrete consequence is in OpenAI's Appendix C: a circuit lower bound, ENP ⊄ SIZE(O(n)), which follows from Williams' 2013 theorem plugging in a deterministic subexponential-time 3-SAT algorithm — exactly what these papers supply. Faster satisfiability algorithms produce circuit lower bounds; that is the standard trade.
The more careful reading — and the one the video's framing implies without spelling out — is that the damage is bounded. SETH falls too, but Orthogonal Vectors does not, and a large share of fine-grained complexity lower bounds (edit distance, LCS, dynamic problems) are proven under OV rather than ETH. Anthropic was explicit about not counting those papers, and reporters who wrote "hundreds of results collapse" should have written "hundreds of results lose their hypothesis, some of which have replacements".
| Layer | What the video says | What the primary sources add |
|---|---|---|
| The result | Eth is false; two labs, same day | Deterministic 2o(n) counting algorithm for #k-SAT, polynomial space, two distinct proofs |
| Verification | Lean accepted both; nobody has read all of it | Two kernels, three standard axioms, 1,050 modules, statements unchecked by machine, no human reviewer named |
| Practical effect | None below 1010,000 variables | No improvement under n > 1010 in the n-only bound; "nothing about practice", stated in the paper |
| Collateral damage | Hundreds of papers need new proofs | 800+ ETH/SETH-conditional results; OV-based bounds survive; new circuit lower bound (ENP ⊄ SIZE(O(n))) gained |
| The real bottleneck | Finding people to read proofs | Independent examination led by Impagliazzo, Paturi and Williams; raw data + funded conference agreed by OpenAI |
The verdict to watch is that of Impagliazzo, Paturi and Williams. Until it lands, the correct description of this week is not "AI disproved ETH"; it is "two labs published a claimed refutation, with machine-checked proofs, and the people who invented the hypothesis have agreed to explain it to the field".
✅ Claims checked
Every figure in this article was checked against the papers, the repositories and independent reporting — not against the transcript. Where the video and the primary source differ, the primary source wins and the difference is noted.
| Claim | Verdict | Where it was checked |
|---|---|---|
| OpenAI's model found the result on 16 October 2026; Lean accepted it the next day | Verified | OpenAI history.md; The Next Web (26 Oct) |
| OpenAI paper is titled The Exponential Time Hypothesis is False | Verified | paper.pdf, openai/math preprints/…-October-25-2026 |
| Anthropic's paper is authored by "Claude" and dated 26 October 2026 | Verified | paper.pdf, eth/README.md |
| Core algorithm found with 14M output tokens and no human input | Verified | Anthropic paper, "Provenance" paragraph |
| The Lean proof is "over a thousand files" | Verified | 1,052 .lean files in eth/; 1,050 modules built |
| Written by AI models, reviewed by other instances of the same models, no person known to have checked it | Verified, verbatim | Anthropic paper, "What has been checked" |
| More than 800 papers prove results only under ETH or a hypothesis implying it | Verified | Anthropic paper, literature search; OV-based results excluded |
| The method only beats brute force above 1010,000 variables | Verified | Anthropic paper §1 (m = 5n case); reading the bound alone needs 1010 |
| Best 3-SAT algorithms are around 1.3n | Verified | 1.328n deterministic (Liu 2018), 1.308n randomized, as cited in the paper |
| The three checkers say their involvement is not certification | Verified | Open letter, quoted by The Next Web |
| OpenAI agreed to release raw data and fund a conference; group has no NDAs and is unpaid | Verified | Williams on X, reported by The Next Web |
| Ryan Williams put ETH's odds at 70% in 2019 | Unverified | No primary source located; presented here as the video's claim, not as fact |
| "Hundreds of results lose the ground they stand on" | Partly true | 800+ ETH/SETH-conditional results affected; Orthogonal-Vectors-based bounds are untouched |
| Two labs, same date, "no human help" | Verified for discovery | Anthropic: presentation was human-assisted after discovery. Discovery: model-only, both labs |
| Also published that day: local smoothing/Kakeya and four-dimensional Yang-Mills claims | Verified (not in the video) | OpenAI history.md; The Next Web. The physics group withheld its AI output to write it up itself |
Transcript notes. The auto-captions render "Paturi" correctly but omit the hyphenated name of the joint 2001 paper's third author, Francis Zane, and transcribe "ETH OpenAI took off on Google" where the intended phrase is "ETH OpenAI" as a search query. No proper noun in the video required correction; the technical vocabulary (3-SAT, Lean, PPSZ, Impagliazzo, Paturi) came through cleanly, which is unusual and was checked line by line against the papers.
🔑 Key takeaways
- Two independent claims, one date. OpenAI's and Anthropic's internal models both found (16 October 2026) a deterministic subexponential algorithm for counting satisfying assignments of k-CNF, which would refute the Exponential Time Hypothesis. Neither company can prove who was first.
- "Disproved" is doing too much work. The checkers — Impagliazzo, Paturi and Williams, i.e. the hypothesis's own authors — said in writing that their involvement is not certification. Treat this as a claim under examination.
- ETH is the load-bearing assumption, not a curiosity. More than 800 papers prove their own results only under ETH or something implying it; SETH falls with it, but Orthogonal-Vectors-based lower bounds survive.
- Lean checks derivations, not meanings. Both proofs pass the kernel (and NanoDA via Comparator), but no machine can confirm that the formal statement says what the paper claims.
- Anthropic's honesty is the story. Its Lean development was written by models, reviewed by other instances of the same models, and no person is known to have checked it. That sentence is in the paper.
- Nothing practical changes. The speed-up only appears past 1010,000 variables (at m = 5n); the paper says outright it says nothing about solving formulas in practice, and Fortnow expects little effect on real solvers.
- The real bottleneck moved. Finding proofs is now cheap; certifying that a formal statement means what it should, and reading the listing, is the scarce resource. Hence the demand for raw data and a funded conference.
- P vs NP is untouched. Subexponential is not polynomial; no complexity class collapsed. Any headline implying otherwise is wrong.
- Bonus consequences. OpenAI's Appendix C derives a circuit lower bound (ENP ⊄ SIZE(O(n))) and subexponential inversion for Boolean maps — the kind of collateral gain that makes the result valuable even if the headline claim were withdrawn.
- Check the second lab. The coverage pattern here — first mover gets the headline, simultaneous discoverer gets a footnote — is the thing to watch for as AI research announcements speed up.
🔗 Resources & links
Primary sources
- OpenAI — "The Exponential Time Hypothesis is False" (PDF, dated 17 October 2026, revised 25 October 2026)
- openai/math — release history (entry for 26 October 2026)
- openai/math repository — 721 manuscripts, 373 families, ~42% of top-line results formalised; pairs with the README and overview
- Anthropic — "A 2o(n) Time Algorithm for 3-SAT" — paper,
MainResults.lean, 1,050-module Lean proof, Comparator config - Anthropic paper (direct PDF) — provenance and "what has been checked" are in §1 and Appendix E
- OpenAI — "Working with academic communities to build scientific understanding" (26 October 2026)
Independent reporting and tools
- The Next Web — OpenAI says its AI model has disproved the Exponential Time Hypothesis (26 October 2026; carries the checkers' open letter and the Kakeya / Yang-Mills results)
- Runtimewire — Anthropic posts its own ETH refutation hours after OpenAI (27 October 2026; Lance Fortnow's reaction)
- The checkers' open letter (Impagliazzo, Paturi, Williams)
- Lean — the proof assistant both labs used; Comparator and elan are the tools the READMEs point to for re-checking