top of page

Did AI Disprove the Exponential Time Hypothesis? OpenAI vs Anthropic Explained

Writer: Shaikhmuizz javed
Shaikhmuizz javed
Nov 11
19 min read

By Muizz Shaikh | AI Enthusiast and Digital Technology Professional, FourfoldAI | Last updated: November 11, 2026



On October 26, 2026, OpenAI posted a paper titled "The Exponential Time Hypothesis Is False." Within hours, Anthropic posted a second paper, credited to a Claude model, that reached essentially the same conclusion by a different route. Both claim a deterministic, subexponential-time algorithm that counts the solutions of 3-SAT formulas, and both ship a Lean 4 formalization. If the claims hold, the Exponential Time Hypothesis (ETH), the quantitative assumption behind hundreds of hardness results, is false.


FourfoldAI graphic asking if AI disproved exponential time hypothesis, with OpenAI and Claude logos, 3-SAT, growth graph, verified proof.

"If they hold" is the operative phrase. As of November 11, 2026, neither paper has been peer reviewed, and the review group led by the hypothesis's own authors has not published a verdict. This article separates what is claimed, what is machine-checked, and what the theory community has actually confirmed.


Key Findings: Did AI Actually Disprove ETH?

Short answer: not yet, in the sense that matters to mathematicians. Two AI-generated proofs exist, both compile in Lean, and no one has publicly found a flaw. That is strong evidence. It is not the same as acceptance.


  • What OpenAI claims: a deterministic algorithm that counts satisfying assignments of any fixed-width k-CNF formula, in polynomial space, in time (n+m)^O_k(1) · 2^(O_k(n · log log n / √log n)). Its manuscript is dated October 17 and revised October 25.

  • What Anthropic claims: a deterministic algorithm for #3-SAT, and more generally #k-SAT, with a matching headline bound. Claude is credited as author, and the paper says the core algorithm was found on October 16 with no human input.

  • What Lean 4 proves: that each formal statement follows from Lean's axioms. It does not prove the formal statement says what the English paper says.

  • The bound gap: OpenAI's Lean scope note records a weaker bound than its manuscript headline. Both are subexponential, but they are not interchangeable.

  • What stays open: P versus NP. A subexponential bound is still far slower than any polynomial.

  • Status: Impagliazzo, Paturi, and Williams are running an open examination. They have said their involvement is not a certification.


What Is the Exponential Time Hypothesis (ETH)?


Formulation and Origins

3-SAT asks a simple question. Given a formula built from clauses of three true-or-false variables joined by OR, can you assign values so every clause holds at once? Brute force tries all 2^n assignments, and each added variable doubles the work.

Russell Impagliazzo and Ramamohan Paturi proposed ETH in a 2001 paper, and a companion paper with Francis Zane tied the variants together. The standard form says there is some constant c > 0 such that no algorithm solves 3-SAT in time O(2^(cn)). Put differently, 3-SAT cannot be solved in 2^o(n) time. The exponent may shrink, but only down to a fixed fraction of n.

Decades of algorithm design fit that picture. According to DataCamp's summary of the pre-October state of the art, the best deterministic 3-SAT algorithm ran in roughly 1.328^n and the best randomized one in roughly 1.308^n. Those are big improvements over 2^n. They are still exponential.


Infographic titled AI vs. the Exponential Time Hypothesis compares OpenAI and Anthropic breakthroughs, with charts and red callouts.

ETH vs. SETH

The Strong Exponential Time Hypothesis (SETH) says something sharper. As clause width k grows, the best base for k-SAT creeps toward 2. In symbols, for every ε > 0 there is a k where k-SAT cannot be solved in 2^((1−ε)n) time.

The logic runs one way. SETH implies ETH. So refuting ETH invalidates SETH, but refuting SETH would leave ETH intact. Anthropic's paper says this directly: its refutation of ETH takes SETH down with it.


The Architectural Role of ETH

ETH became useful because 3-SAT converts into so many other problems. Researchers use it as a quantitative anchor for statements of the form "this problem cannot be solved faster than X unless ETH fails." That includes tight bounds for graph problems like Independent Set, Clique, and Vertex Cover, and lower bounds in parameterized algorithms and fine-grained complexity.

OpenAI says the conjecture appears in "hundreds of papers." Anthropic reports that a literature search run by Claude found more than 800 papers proving at least one result under ETH or a hypothesis that implies it. Anthropic's count excludes results that rest on assumptions the new work does not touch, such as the Orthogonal Vectors hypothesis.


Inside OpenAI's 3-SAT Refutation Claim


From Decision to Counting

Here is the first surprise. OpenAI did not build a better satisfiability solver. It built a counter.

The algorithm computes the exact number of satisfying assignments, a problem known as #3-SAT, or #k-SAT for general clause width k. Counting is #P-complete, which makes it at least as hard as deciding satisfiability. A formula is satisfiable exactly when its count is positive. So a subexponential counter automatically gives a subexponential decider, and the 3-SAT case refutes ETH. It also refutes #ETH, the counting analogue.


Mathematical Mechanics

Be careful here, because the sourcing is thinner than the headlines suggest. The brief behind this article described OpenAI's machinery as polynomial interpolation, variable separation, and deterministic tensor-network contractions on bounded-degree formulas. I could not confirm that description from the manuscript itself. One secondary summary credits polynomial interpolation as part of the core technique, and Ryan Williams has told reporters that most of the proof looks routine while "two or three" parts look unfamiliar. Beyond that, I am not going to guess at the mechanism. The tensor-network and rank language is documented for Anthropic's paper, covered in the next section.

What the manuscript itself states is the result. For each fixed k ≥ 2, the algorithm counts satisfying assignments of k-CNF formulas using polynomial space. Theorem 1.1 gives its bounds for n ≥ 20.


The Bound Discrepancy

Per Kingy AI's tracker, which compared the artifacts directly, three runtime statements are in play:

  • Revised manuscript, general case (m clauses): (n+m)^O_k(1) · 2^(O_k(n · log log n / √log n)).

  • Documented Lean scope: (L+1)^O_k(1) · 2^(O_k(n · (log log n)² / √log n)), where L is the bit length of the input.

  • Revised manuscript, sparse formulas (m ≤ D·n): (n+m)^O_k,D(1) · 2^(O_k,D(n / √log n)).

Compare the first two. The Lean bound carries an extra factor of log log n in the numerator. Both exponents are o(n), so both are subexponential and both refute ETH. But a proof of the weaker statement does not automatically establish the sharper one.


OpenAI's own Lean scope note separates the two, and Kingy's reviewers warn against describing the manuscript's sharper exponents as covered by the Lean theorem. Lance Fortnow's blog makes the same point in a parenthetical: the Lean proof gives a slightly weaker bound. This is not scandal. It is the normal gap between a paper and its formalization, and it is exactly why discrepancies between text and artifact deserve scrutiny.


How Anthropic and Claude Independently Approached 3-SAT


The Provenance

Anthropic's paper, "A 2^o(n) Time Algorithm for 3-SAT," runs 49 pages and lists the author as "Claude (Anthropic)." Its provenance statement says an internal Claude research model found the core algorithm on October 16, using 14 million output tokens and no human input. Anthropic researchers then worked with Claude to improve the presentation.

The paper also notes, in its own words, that an internal OpenAI model independently and concurrently claims a similar result. Neither lab has independently confirmed the other's date. Jelani Nelson, a Berkeley theorist who read Claude's proof before release, wrote that both proofs appear to reach roughly exp(O(n / √log n)).


Algorithmic Formulation

The brief for this article assumed Anthropic attacks the 3-SAT decision problem through graph-theoretic partitioning of hypergraphs. The sources say otherwise on both counts. Anthropic's algorithm also solves the counting problem, and its stated tools are tensor networks and rank arguments. I found no source describing a hypergraph-partitioning method.


The headline bound matches OpenAI's general case. Anthropic's README states a refinement: for k-CNF formulas without repeated clauses, a deterministic Turing machine counts solutions in 2^(O(min{k² · n · log log n / √log n, k · m / √log m})) steps. The second term depends on the clause count m, which helps on formulas with few clauses.


Two further claims stand out. The paper says it refutes SETH as a consequence, but does not refute the Orthogonal Vectors hypothesis. It also reports consequences for specific graph problems, with subexponential algorithms in theory for Independent Set, Clique, Vertex Cover, and Dominating Set, and a new circuit lower bound for the class E^NP. Those consequences come from the paper's own account via secondary summaries, and I have not verified them line by line.


Public Artifacts

The repository is public under anthropics/formal-math. Its README says the Lean 4 formalization spans 1,050 modules, depends only on Lean's three standard axioms, and is checked by both the Lean kernel and a second, independently written kernel called nanoda. It also says no machine checks that the short statement file matches the paper, and that the formalization was written by AI models and reviewed by other instances of the same models. At the time of writing, the paper says, no person was known to have checked it.

Anthropic is blunt about practice, too. The README describes the result as purely asymptotic. And it claims a Claude model run at high effort can rederive a weaker version of the refutation from a short technical sketch, which is a striking claim about reproducibility that nobody outside Anthropic has tested.


OpenAI vs. Anthropic: Comparing the Algorithms and Proofs


Both labs reached the same asymptotic neighborhood, roughly 2^(n/√log n) with lower-order terms in the exponent. The interesting differences sit in what each artifact certifies and how each lab describes its own evidence.


OpenAI's package is a manuscript plus a Lean file whose scope note openly records a weaker bound than the paper. Its Lean target does not mention ETH by name. It proves that a machine correctly outputs the satisfying-assignment count within the stated time and space bounds, leaving ETH's failure as a corollary. Anthropic's package is built the other way around. Its formal statement file defines both the failure of ETH and the counting theorem on Mathlib's Turing machines, and it publishes the differences between that statement and the paper in an appendix.


Neither approach is automatically safer. A statement that names ETH is easier to audit against the English hypothesis. A statement about a counting machine is more modest but leaves a longer logical hop to ETH.


Infographic comparing OpenAI vs. Anthropic claims on AI proof complexity, with charts, diagrams, and bold black headings.

Table 1: Technical and Algorithmic Comparison

Dimension

OpenAI Approach

Anthropic Approach

Primary Target Problem

#k-SAT counting (fixed k ≥ 2); decides 3-SAT as a consequence

#k-SAT counting, #3-SAT headline; decides 3-SAT as a consequence

Claimed Time Bound

Manuscript: (n+m)^O_k(1) · 2^(O_k(n · log log n / √log n)); sparse case 2^(O_k,D(n / √log n))

2^(O(n · log log n / √log n)) headline, with a min{...} refinement that also depends on clause count m

Space Complexity

Polynomial space stated in the manuscript

Not confirmed in the sources I could open; check the paper before quoting a figure

Core Technique

Not confirmed from the manuscript; one secondary summary cites polynomial interpolation

Tensor networks and rank arguments, per secondary summaries of the paper

Lean 4 Artifact Scope

Weaker bound with an extra (log log n)² factor, documented in a scope note; target proves a counting machine's correctness

1,050 modules; statement file defines ETH's failure and the main counting theorem on Mathlib Turing machines

External Validation Status

Open examination led by Impagliazzo, Paturi, Williams; no verdict; not peer reviewed

Not stated in the release; same community review applies; not peer reviewed

Note one correction to the brief, visible in the first row. The framing "#3-SAT counting versus 3-SAT decision" does not hold: both labs claim counting algorithms. The space row also differs from the brief, which assumed polynomial space for both. I could confirm it only for OpenAI.


The Proof Verification Spectrum: What Does Lean 4 Actually Guarantee?


What Lean 4 Checks

Lean is a proof assistant. A small trusted kernel type-checks every step of a formal proof, so a proof that compiles has derived its stated theorem from Lean's axioms and nothing else. That removes a whole class of failure: no hand-waved step, no hallucinated lemma, no arithmetic slip hiding on page 41.

Think of the kernel as a compiler for mathematics. It guarantees the program does what the code says. It cannot guarantee the code is the program you meant to write.


The "Lean Gap"

Three failure modes survive a green checkmark.

  • Vacuous proofs. If a definition is trivialized so that the premise of P → Q can never hold, the implication is true and useless. The proof compiles and says nothing.

  • Theorem statement mismatch. The formal statement can diverge from the English theorem in the PDF. A wrong definition of "time," "machine," or "3-SAT instance" can make a correct proof of the wrong thing.

  • Axiom ingestion. A formalization can slip in unvetted axioms, or leave unfinished steps marked with the placeholder sorry. Auditors check that the proof depends only on Lean's three standard axioms and contains no placeholders.


Anthropic's own README describes the second failure mode as the core residual risk, and the artifacts show the issue in practice. Anthropic's Lean statements measure steps of a deterministic Turing machine on Mathlib's machine model. Translating the input formula into that format, and simulating Mathlib's machine in the paper's computational model, are described as standard steps that sit outside the formal proof. Kingy's tracker lists third-party reports describing replay and bridge work on that gap, and a status summary dated around November 5 says outside volunteers formalized that bridge. Treat those as promising but unrefereed.

This is the spot where the question of human verification, reproducibility, and auditability matters most. Our guide to agentic AI governance and shadow AI controls covers how organizations build that kind of review layer into automated systems, and the same logic applies here. If you want the broader argument for why formal proof tools matter for AI-generated science, see our earlier piece on OpenAI's Lean breakthrough and the shift to verifiable AI science.


A Visual Framework: Four Questions Before You Believe a Formal Proof

Use this workflow for any AI-generated proof, in this order:

  1. Does it compile? Build the repository on a clean machine and confirm a second kernel accepts it.

  2. Is it clean? Confirm the proof depends only on Lean's three standard axioms and contains no sorry placeholders.

  3. Is the statement faithful? Read the short statement file and ask whether it says what the English hypothesis says. This is a human judgment.

  4. Do experts agree? Wait for independent specialists to read the argument, not just the code.

Steps 1 and 2 are mechanical. Steps 3 and 4 are where discoveries become knowledge.


Table 2: Claimed vs. Formalized vs. Verified Status Matrix (as of November 11, 2026)

Verification Tier

OpenAI Artifact

Anthropic Artifact

Community Consensus Status

Manuscript Publicly Released

Yes. About 67 pages, dated Oct 17, revised Oct 25; posted Oct 26

Yes. 49 pages, dated Oct 26; repository release Oct 27 UTC

Both public; none peer reviewed

Lean Formalization Compiles

Yes, per OpenAI. Public Lean files; scope note documents a weaker bound than the manuscript

Yes, per Anthropic CI: 1,050 modules, Lean kernel plus second kernel (nanoda)

Volunteers report replaying both under independent checkers; not a formal audit

Zero Custom Axioms Verified

Not confirmed in the sources I reviewed

Reported: only Lean's three standard axioms (company-reported; Kingy did not read every CI log)

No independent axiom audit located

Theorem Statement Equivalence Checked

Open. Scope note and statement files published for inspection

Open. README says no machine checks the statement against the paper

Under examination by the Impagliazzo–Paturi–Williams group; no verdict

Independent Human Peer Review

None completed

None completed; paper says no person was known to have checked the Lean files at writing

No consensus; expert reactions are informal


Theoretical Fallout: What Breaks If ETH Is False?


The Domino Effect on Lower Bounds

Start with what does not break: published theorems. Fortnow's point is that results proved under ETH or SETH are not wrong. The implication still holds. What changes is the standing of the assumption underneath them. A statement of the form "if ETH, then no fast algorithm for X" loses its force, because the "if" no longer looks plausible.

Many conditional lower bounds in parameterized algorithms rest on ETH. With ETH gone, researchers have to ask, case by case, whether a weaker assumption still supports the bound. Some probably will. Others may become open problems again. Anthropic's paper adds a practical edge: its method yields faster-than-expected theoretical algorithms for several classic graph problems, which turns "this was proven hard" into "this was hard to beat, until now."


Fine-Grained Complexity Reassessment

Fine-grained complexity studies exact polynomial exponents, as in whether Longest Common Subsequence or Edit Distance can beat quadratic time. Many of those results are conditional on SETH, directly or through the Orthogonal Vectors hypothesis. SETH falls with ETH, so the foundation shifts.


But Anthropic's paper states plainly that its theorem does not refute Orthogonal Vectors. Where a hardness result runs through OV rather than SETH directly, it stands on ground this work does not touch. I have not seen a verified problem-by-problem accounting for LCS, Edit Distance, or Fréchet Distance, and I would treat any confident claim about them as premature. Expect that accounting to arrive from specialists over the coming months.


Early signs of the field regrouping already exist. On November 1, Ryan Williams opened a public place to announce follow-on results, and a spreadsheet of new algorithms derived from the refutation was circulating by November 2, according to Emergent Mind's running explainer.


What Stays Intact

P ≠ NP remains completely open. Subexponential time, 2^o(n), is still strictly super-polynomial. The new algorithm does not come near a polynomial bound, and OpenAI's own paper says its result does not bear directly on P versus NP. Disproving ETH removes one road to proving P ≠ NP. It does not prove P = NP.

Fortnow also stresses a boundary on the other side: the algorithm applies to 3-SAT and its relatives, and gives nothing new for Subset Sum or the Traveling Salesman Problem.


The Engineering Reality: Why 2^o(n) Solvers Won't Replace MiniSat Tomorrow


The Asymptotic Trap

Big-O notation hides constants, and these results hide enormous ones. A bound like 2^(n/√log n) describes the shape of a curve as n heads to infinity. It says nothing about where the curve crosses brute force.


The Curse of Constants

Set the hidden constants to 1 and work the arithmetic. At n = 500 variables, the natural log of 500 is about 6.2 and its square root about 2.5, so the exponent n/√ln n comes to roughly 200. That suggests 2^200 against brute force's 2^500. It looks like a miracle. It is a mirage, because the real bound multiplies the exponent by a constant that depends on k and that the papers leave unspecified. (That is my own back-of-envelope calculation for the shape of the curve, not a result from either paper.)


The papers themselves are more honest than the arithmetic. Anthropic states that its result says nothing about solving formulas in practice. For 3-CNF formulas with five clauses per variable, reporting from both DataCamp and CellCog says the bound beats exhaustive search only when n exceeds about 10^10,000. For the fully general case, the two outlets give different figures, with CellCog citing 10^108 and DataCamp citing a number of roughly 100 million digits, so check the paper's own table before repeating either. The paper also estimates its general approach would not help below roughly 10 million variables.


Why Theory Algorithms Often Don't Ship

Modern CDCL (Conflict-Driven Clause Learning) solvers such as CaDiCaL and Kissat do not win by worst-case guarantees. They win by learning from conflicts and exploiting structure in real instances, which is why they handle industrial formulas that look hopeless on paper. Hardware verification, scheduling, and formal verification pipelines live in that regime.

A subexponential worst-case algorithm and a fast practical solver are answers to different questions. The first bounds the worst formula anyone could write. The second wins on the formulas people actually write. Fortnow has noted that people are discussing whether some version of the refutation could help in practice, but that remains speculation. If you run a verification or synthesis workflow, nothing changes on Monday.


The Paradigm Shift in Automated Mathematical Reasoning



The more durable story is about method. Two independent systems, on the same date by their own accounts, produced a result that specialists treated as a surprise. Sebastien Bubeck of OpenAI called it perhaps the biggest surprise in his 20 years of following the field. Impagliazzo, a co-proposer of ETH, said it is not yet 100 percent certain and described the news as shocking.


The Synergy

The division of labor is becoming clearer. Language-model reasoning engines generate high-level proof sketches, lemmas, and transformations at a scale no human team could search. Interactive theorem provers like Lean verify each logical step without trusting the generator. One side proposes. The other refuses to accept anything it cannot check.


The Emerging Pipeline

Read the October artifacts as the first public look at a pipeline: hypothesis, symbolic search, formal Lean encoding, human review. The first three stages took days. The fourth is taking weeks and counting, and it is the one that cannot be automated away, because a human has to decide whether the formal statement means what the field means.


That tension runs through the wider debate about autonomous research. If a model can find and formalize a result with no human input, as Anthropic reports, who is accountable for the claim? Our analysis of the autonomy loophole in AI coding agents explores where unsupervised AI work starts to outrun human oversight, and the ETH episode is a clean test case: a verified artifact, an unverified claim.


Tool use matters here too. These artifacts were released as public repositories with continuous-integration builds, so anyone can rerun them. That is reproducibility by construction, and it echoes the concerns we cover in MCP and agentic security, where automated script execution and repository analysis need clear trust boundaries.


Limitations, Axiomatic Blindspots, and Open Questions


Here is what remains unverified.

  • No completed expert verdict. The Impagliazzo–Paturi–Williams group has not reported. Their open letter says their role should not be read as certification.

  • Statement equivalence. Whether each Lean statement captures standard ETH is still a human judgment.

  • OpenAI's sharper bound. The manuscript's stronger exponent is not covered by the Lean theorem.

  • Axiom audits. Anthropic reports only Lean's three standard axioms. I found no equivalent independent audit for OpenAI's files.

  • Mechanism details. I could not confirm OpenAI's technique from primary sources, and Anthropic's space bound is not confirmed in what I read.

  • Dates and provenance. Both October 16 discovery dates are self-reported and unconfirmed.

  • Source quality. Much of the public commentary is secondary. Where outlets disagreed, I said so.


Research Methodology and Verification Sources


I cross-referenced the public manuscripts and repositories from both labs against independent trackers, expert commentary, and news coverage. For OpenAI, that meant the announcement, the manuscript's stated bounds, and the Lean scope note as summarized by Kingy AI's record, which compared the artifacts directly. For Anthropic, it meant the paper, the repository README, and the Lean statement files as described by several outlets.


I did not rebuild either Lean project, run either algorithm, or audit the dependency graphs myself. Where I describe CI results or axiom use, those are company-reported or tracker-reported. For expert reactions I relied on Lance Fortnow's blog, which I read directly, and on press reports of statements by Williams, Impagliazzo, and others. I treated statements from the labs as claims and statements from outside reviewers as evidence. The facts here are current as of November 11, 2026, and this story is moving daily.

One disclosure: this article was drafted with assistance from Claude, a model made by Anthropic, which is one of the two labs under examination. I held both labs to the same sourcing standard, and every factual claim traces to the references below.


Frequently Asked Questions


What is the Exponential Time Hypothesis?

The Exponential Time Hypothesis (ETH) is a 2001 conjecture by Impagliazzo and Paturi stating that 3-SAT cannot be solved in subexponential time. Formally, some constant c > 0 exists such that no algorithm solves 3-SAT in O(2^(cn)) time. Researchers use it to prove conditional hardness for hundreds of other problems.


Did AI disprove the Exponential Time Hypothesis?

Two AI labs claim so, but it is not yet accepted. OpenAI and Anthropic each published a subexponential counting algorithm with a Lean proof. No flaw has been publicly found, yet no peer review is complete, and an expert group led by ETH's authors is still examining both claims.


Does disproving ETH mean P = NP?

No. Disproving ETH shows 3-SAT admits a 2^o(n) algorithm, which is still far slower than any polynomial. P versus NP asks about polynomial-time solvability and remains open. OpenAI's paper says its result does not bear directly on that question, and its president said P probably still does not equal NP.


What is the difference between ETH and SETH?

ETH says 3-SAT needs 2^(cn) time for some c > 0. SETH is stronger: as clause width k grows, the best base for k-SAT approaches 2. SETH implies ETH, so refuting ETH also refutes SETH, but refuting SETH alone would leave ETH standing.


What is the difference between 3-SAT and #3-SAT?

3-SAT is a decision problem asking whether any assignment satisfies a formula. #3-SAT asks for the exact number of satisfying assignments and is #P-complete, so it is at least as hard. A counting algorithm also decides satisfiability, since a formula is satisfiable exactly when its count is positive.


What does Lean 4 prove in an AI-generated paper?

Lean 4 proves that a formal theorem statement follows logically from its axioms, checked by a small trusted kernel. It does not prove the formal statement matches the English paper. Anthropic's README says no machine checks that match, so humans must still read the statement files.


Can an AI formal proof contain errors?

Yes, in a limited sense. A compiled Lean proof cannot contain a logical gap, but it can prove the wrong statement, rest on a vacuous definition, or add unvetted axioms. Errors move from the proof steps to the definitions, which is why human review of the statement remains essential.


Why are theoretical subexponential algorithms slow in practice?

Asymptotic bounds hide large constants and only describe behavior as input size grows without limit. Anthropic's paper says its bound beats brute force only for astronomically large inputs, about 10^10,000 variables for formulas with five clauses per variable. Practical solvers exploit structure instead of worst-case guarantees.


What is fine-grained complexity?

Fine-grained complexity studies exactly how fast problems can be solved, such as whether edit distance beats quadratic time. It builds conditional lower bounds from hypotheses like ETH, SETH, and Orthogonal Vectors. Anthropic says its result refutes ETH and SETH but not Orthogonal Vectors.


Did OpenAI and Anthropic collaborate on this result?

No. Both labs describe the work as independent and concurrent, and both date their model's discovery to October 16, 2026. Anthropic's paper says an OpenAI model independently claims a similar result. Neither lab has independently confirmed the other's timeline, and the two papers take different routes.


What happens to cryptography if ETH is false?

Nothing immediate. OpenAI says it checked whether the algorithm breaks real cryptosystems and is reasonably confident it does not. Standard cryptography rests on specific hardness assumptions rather than ETH, though researchers will re-examine analyses that use it. The new bound only wins at astronomically large sizes.


Has the academic community officially accepted the ETH refutation?

Not yet. As of November 11, 2026, neither paper is peer reviewed and no verdict has been published by the Impagliazzo–Paturi–Williams group. Some experts, including Lance Fortnow, already treat the hypothesis as effectively dead, though Fortnow says he has not verified the proof himself.


Conclusion: A Watershed Moment for AI-Assisted Theory


The Exponential Time Hypothesis may be false. The evidence is better than anything a skeptic would have demanded a month ago: two independent AI-generated proofs, two public Lean artifacts, no flaw found yet, and a respected expert group reading closely. Fortnow's verdict is that it is safe to assume ETH is toast. That is a respected view. It is not a certified one.


This is not the end of complexity theory. P versus NP is untouched, practical SAT solving is unchanged, and the real work now falls to human specialists who must rebuild which hardness results still stand. What changed is the research workflow. Automated reasoning arrived as a legitimate partner in pure mathematics, and it produced something checkable.


Watch three signals: a verdict from the review group, independent reproduction of the Lean statements, and any tightening of the bound. Until then, hold two thoughts together. The proofs compile, and the field has not yet said they are right.


Explore more at FourfoldAI. If this kind of verification-first analysis is useful to you, our deep dives on enterprise AI infrastructure, agentic systems, and verification architectures are at fourfoldai.com.


References

This article is backed by authoritative sources and research, including the primary papers, repositories, and expert commentary listed below. Links were live when checked on November 11, 2026.


  1. OpenAI, "Working with academic communities to build scientific understanding" (announcement): https://openai.com/index/building-scientific-understanding-with-academic-communities/

  2. OpenAI, "The Exponential Time Hypothesis Is False" (manuscript, revised October 25, 2026): https://github.com/openai/math/blob/7ef5c0cc5ca4b0e072b7a050fca09ab24bc6fa3a/preprints/The-Exponential-Time-Hypothesis-is-False-October-25-2026/paper.pdf

  3. OpenAI, Lean scope note 378: https://github.com/openai/math/blob/7ef5c0cc5ca4b0e072b7a050fca09ab24bc6fa3a/lean/docs/378.md

  4. Anthropic, "A 2^o(n) Time Algorithm for 3-SAT" (paper, via Hexagon): https://hexagonmath.org/pdf/2610.00577v1

  5. Anthropic, formal-math repository, ETH folder (README and Lean 4 formalization): https://github.com/anthropics/formal-math/tree/16a5ce41304fcdaea4e0be7c132e1c361dc26da5/eth

  6. Lance Fortnow, "The Exponential Time Refutation," Computational Complexity blog, October 28, 2026: https://blog.computationalcomplexity.org/2026/10/the-exponential-time-refutation.html

  7. Kingy AI, Breakthrough Tracker record on OpenAI's ETH-refutation claim (revised November 4, 2026): https://kingy.ai/mathematics-science-breakthrough-tracker/records/cs-exponential-time-hypothesis-refutation-openai-2026/

  8. Emergent Mind, "OpenAI and Anthropic say AI refuted the Exponential Time Hypothesis" (updated November 2, 2026): https://www.emergentmind.com/exponential-time-hypothesis

  9. DataCamp, "AI Refutes the Exponential Time Hypothesis: What This All Means" (November 6, 2026): https://www.datacamp.com/blog/ai-exponential-time-hypothesis

  10. CellCog, "Claude Refuted ETH Too: Anthropic's 3-SAT Paper Explained" (October 27, 2026; vendor runs on Claude and discloses the conflict): https://cellcog.ai/blog/claude-refutes-eth-3-sat/

  11. The Next Web, "OpenAI says its AI model has disproved the Exponential Time Hypothesis": https://thenextweb.com/news/openai-exponential-time-hypothesis-false-kakeya-yang-mills

  12. Magica, "Anthropic publishes Claude's claimed ETH refutation": https://magica.com/news/anthropic-claude-exponential-time-hypothesis-claimed-refutation

  13. FourWeekMBA, "Anthropic Says Claude Also Refuted ETH, Using 14M Tokens": https://fourweekmba.com/ai-anthropic-says-claude-also-refuted-eth-using-14m-tokens/

  14. Wikipedia, "Exponential time hypothesis" (background and definitions): https://en.wikipedia.org/wiki/Exponential_time_hypothesis

  15. "Superlinear Lower Bounds Based on ETH" (definitions of ETH and SETH), arXiv: https://arxiv.org/pdf/2008.06805


Disclaimer


Disclaimer: This article is for informational and educational purposes only and reflects publicly available information as of November 11, 2026. The mathematical claims discussed are unrefereed and may change as expert review proceeds. It is not professional, legal, or financial advice. For the full disclaimer, visit https://www.fourfoldai.com/disclaimer.


About the Author


Muizz Shaikh is an AI enthusiast and digital technology professional at FourfoldAI. He is passionate about exploring AI tools, industry trends, and practical applications of emerging technologies. Through FourfoldAI, Muizz contributes to simplifying artificial intelligence for businesses and learners. Connect with him on LinkedIn: linkedin.com/in/muizz-shaikh-45b449403/


  • © 2026 FourfoldAI. All rights reserved.

Comments


bottom of page