ResearchPapers, evidence & method
OpenAI and Anthropic each say internal AI models refuted the Exponential Time Hypothesis
OpenAI and Anthropic each say an internal model found an algorithm that solves 3-SAT faster than the Exponential Time Hypothesis allows, backed by Lean-checked proofs. The result is theoretical, offers no practical speedup, does not settle P vs NP, and awaits human expert review.
From the TechCrunch AI article of October 27, 2026 and cited sources: Both labs date their discoveries to October 16, 2026. [6] [7]
AT Pulse research deskPublished · Updated · 5 min read · AI-assisted analysisAI-assisted, not human-edited. Methodology Corrections Who owns this site
- Original source
- TechCrunch AI article, independent perspective
- Brief by
- AT Pulse research desk AI-assisted; publisher and contact on the desk page
- Studies
- arXiv 2102.02624 (Feb 2021) [14] date from arXiv ID
- When
- October 27, 2026 article published
- Covered
- Oct 28 edition
- Evidence
- 15 sources across 15 sites
Reach: not measured yet
Both labs date their discoveries to October 16, 2026. Each describes a subexponential algorithm for k-SAT with a running time of roughly 2^O(n·log log n/√log n) in the number of variables. That would contradict the 1999 assumption that 3-SAT needs time exponential in n. Jelani Nelson said the two algorithms reach about the same runtime. Anthropic says its Claude research model found the core algorithm without human input. [6] [7]
Both proofs are posted on GitHub in Lean. They rely only on standard axioms and were checked with the Comparator tool. Anthropic also re-checked its proof with a second, independent Lean kernel. OpenAI's Lean proof certifies a weaker exponent than its paper states. Impagliazzo, Paturi and Williams said in an open letter that their part in the review does not certify the claim. [7] [12] [3]
Nothing changes in practice yet. According to TechTimes, the new algorithm only beats brute force at around 10^10,000 variables. Refuting ETH would not imply P = NP, and the reviewed sources say no changes to SAT solvers or key sizes are justified. The statement that no cryptographic breaks follow comes from OpenAI's own internal check, and no independent check of that point has been published. [6] [2] [8] [1]
Anthropic's paper counts about 800 papers whose lower bounds rest on ETH. The episode is also testing how AI-generated math should be released. OpenAI is holding back its physics proof while external reviewers examine it. OpenAI also acknowledges that picking the first reviewers gives some people access before others. [6] [3] [9]
If the refutation holds, it undercuts conditional lower bounds in roughly 800 papers and shows frontier models producing research-level theory.
Read the full assessment
For now, the evidence is machine-checked proofs awaiting human review, and effects on SAT solvers, cryptography and research norms remain speculative.
Executive brief
Two rival AI labs, OpenAI and Anthropic, each say an internal model found the same thing on the same day, October 16, 2026: an algorithm that would disprove the Exponential Time Hypothesis (ETH). ETH is a 1999 assumption about how hard certain logic puzzles are to solve, and a lot of computer science theory rests on it (TechTimes; lilting.ch). Both labs published machine-checked proofs. No human expert has certified either result yet. The speedup is purely theoretical, and the claim does not settle P vs NP (Decrypt).
What changed and event timeline
OpenAI's first proof release
OpenAI posted a set of math results using the same release-on-GitHub approach it later used for local smoothing. Ryan Williams called that earlier release a "DDOS attack on mathematicians" (;).
Both labs date the discovery
OpenAI says an unreleased internal model produced the refutation. Anthropic says an internal Claude research model found the core algorithm using 14M output tokens and no human input ().
OpenAI finishes the Lean proof
OpenAI says the proof was formalized in the Lean proof assistant one day after discovery ().
OpenAI announces three results
OpenAI announced the ETH refutation, a proof of the local smoothing conjecture, and a physics result. Impagliazzo, Paturi and Williams released an open letter saying their involvement is not a certification of the claim ().
(~03:07 UTC): Anthropic publishes its own refutation
This came hours after Anthropic mathematician Levent Alpöge suggested OpenAI's work drew on existing research (;).
Capabilities and access
- Models: neither model is public. Anthropic credits an internal "Claude research model" (The Next Web; TechTimes).
- Artifacts: the papers and Lean proofs are in the
openai/mathandanthropics/formal-mathGitHub repositories (lilting.ch). - Physics material: the files for OpenAI's physics result are being held back while a group including David Gross reviews them (Popular AI).
Read the full section
- Models: neither model is public. OpenAI calls its system an "internal model" and gives no name. Anthropic credits an internal "Claude research model" (The Next Web; TechTimes).
- Artifacts: the papers and Lean proofs are in the
openai/mathandanthropics/formal-mathGitHub repositories (lilting.ch). - Physics material: the files for OpenAI's physics result are being held back while a group including David Gross reviews them (Popular AI).
Technical analysis for researchers and developers
- Problem: k-SAT, including 3-SAT. ETH says 3-SAT needs time of 2^(cn) for some constant c > 0, where n is the number of variables (Wikipedia).
- OpenAI's bound: poly(n+m)·2^O(n·log log n/√log n), and 2^O(n/√log n) when the number of clauses is linear in n.
- Paper vs Lean gap: OpenAI's Lean proof certifies a weaker exponent, (log log n)², and covers exact counting of satisfying assignments (Popular AI).
Read the full section
- Problem: k-SAT, including 3-SAT. ETH says 3-SAT needs time of 2^(cn) for some constant c > 0, where n is the number of variables (Wikipedia).
- OpenAI's bound: poly(n+m)·2^O(n·log log n/√log n), and 2^O(n/√log n) when the number of clauses is linear in n. Anthropic's bound: the smaller of 2^O(n·log log n/√log n) and 2^O(km/√log m) (lilting.ch).
- Paper vs Lean gap: OpenAI's Lean proof certifies a weaker exponent, (log log n)², and covers exact counting of satisfying assignments (Popular AI).
- Verification: both proofs use only standard Lean axioms and were checked with the Comparator tool. Anthropic also re-checked its proof with nanoda, an independent Lean kernel (lilting.ch).
Claims and evidence
- Both refutations hold: only the labs report this.
- The two algorithms reach about the same runtime: Jelani Nelson said so, as reported by TechTimes.
- No cryptography breaks: OpenAI told Williams it checked and was "reasonably confident" none follow. No independent check has been published (TechCrunch).
Read the full section
- Both refutations hold: only the labs report this. The Lean checks confirm the formal statements, not that those statements faithfully capture ordinary 3-SAT (Popular AI; TechTimes).
- The two algorithms reach about the same runtime: Jelani Nelson said so, as reported by TechTimes.
- No cryptography breaks: OpenAI told Williams it checked and was "reasonably confident" none follow. No independent check has been published (TechCrunch).
- Some proof steps are new: Williams describes two or three "alien-looking" parts alongside routine ones (TechCrunch).
- The two discoveries were independent: no public evidence confirms this. Alpöge's suggestion that OpenAI drew on prior work has not been substantiated in the reviewed sources.
Context and prior work
- Impagliazzo and Paturi formulated ETH in 1999. Both are now helping lead the review of the claims against it (R&D World).
- Anthropic's paper counts about 800 papers whose lower bounds rest on ETH, spanning graph theory, parameterized complexity, databases and communication complexity (TechTimes).
- Earlier refutations have been claimed. A 2021 arXiv preprint said ETH and #ETH were false, but it was never accepted (arXiv 2102.02624).
Read the full section
- Impagliazzo and Paturi formulated ETH in 1999. Both are now helping lead the review of the claims against it (R&D World).
- Anthropic's paper counts about 800 papers whose lower bounds rest on ETH, spanning graph theory, parameterized complexity, databases and communication complexity (TechTimes).
- Earlier refutations have been claimed. A 2021 arXiv preprint said ETH and #ETH were false, but it was never accepted (arXiv 2102.02624).
- Refuting ETH would not imply P = NP (MindStudio).
Limitations, safety and contested findings
- No practical speedup: per TechTimes, the new algorithm only beats brute force at roughly 10^10,000 variables (TechTimes).
- Openness dispute: the Advisory Group on Mathematics and AI asked OpenAI to release the physics proof immediately.
- Uneven access: OpenAI acknowledges that its choice of first reviewers shapes who gets involved first and creates information asymmetry (Unite.AI).
Read the full section
- No practical speedup: per TechTimes, the new algorithm only beats brute force at roughly 10^10,000 variables (TechTimes). Anthropic itself says the result does not establish a real-world speedup (R&D World).
- Openness dispute: the Advisory Group on Mathematics and AI asked OpenAI to release the physics proof immediately. OpenAI deferred to the external review group's decision to hold it back (R&D World).
- Uneven access: OpenAI acknowledges that its choice of first reviewers shapes who gets involved first and creates information asymmetry (Unite.AI).
- Review terms: the reviewers signed no NDAs and are not being paid (KuCoin News).
Business and practitioner implications
- SAT solvers and cryptography: no changes to production SAT solvers or key sizes are justified now, according to the reviewed sources (Decrypt).
- Research capability: two labs reached the same result on the same day, so frontier models may now be able to find publishable theory results.
- Machine-checked ≠ accepted: formal verification lowers the cost of checking a proof, but human review is still needed to accept it as a result.
Read the full section
- SAT solvers and cryptography: no changes to production SAT solvers or key sizes are justified now, according to the reviewed sources (Decrypt).
- Research capability: two labs reached the same result on the same day, so frontier models may now be able to find publishable theory results. Expect a contest over credit and over who sets release norms.
- Machine-checked ≠ accepted: formal verification lowers the cost of checking a proof, but human review is still needed to accept it as a result.
- Planning: Williams has asked OpenAI to fund a conference on how the field's foundations should change (TechCrunch).
The source trail.
Sources (15)
TechCrunch
techcrunch.comMindStudio
mindstudio.aiR&D World
rdworldonline.comOpenAI says AI-written proofs disprove the Exponential Time Hypothesis and prove the local smoothing conjecture
Related coverage; assess separately
pasqualepillitteri.itAI Daily Digest covers OpenAI's ETH and local smoothing proof claims
Related coverage; assess separately
github.com