OpenAI said on 26 October 2026 that one of its AI systems had refuted the Exponential Time Hypothesis, and crypto social media briefly read the headline “ETH is false” as news about Ethereum. It is not. Here ETH stands for a 1999 conjecture in computer science about how hard a logic puzzle called 3-SAT must be, proposed by Russell Impagliazzo and Ramamohan Paturi. OpenAI published a 67-page manuscript and a Lean formalisation in its public GitHub repository, according to its announcement.
The claim has not been reviewed. The three computer scientists OpenAI asked to oversee the checking, Impagliazzo and Paturi of UC San Diego and Ryan Williams of MIT, wrote in an open letter the same day: “Our involvement should not be taken as certification of the claim.” Nothing in the manuscript attacks SHA-256, the hash function behind bitcoin blockchain and earns a reward, which makes rewriting history very expensive.">mining and addresses, or the elliptic-curve signatures that protect bitcoin keys. The paper’s only passage on inverting functions concerns a family of theoretical constructions, and even there it says its result does not rule out one-wayness against polynomial-time algorithms.
Bitcoin traded near $80,850 at 05:43 UTC on 28 October, up 1.39% over 24 hours. Nothing in the market data ties that move to this story.
What OpenAI claims about the Exponential Time Hypothesis
The Exponential Time Hypothesis says that 3-SAT has no subexponential algorithm: there is some fixed constant c above zero such that, in the worst case, deciding a 3-SAT formula with n variables takes at least about 2 to the power of c times n steps. A 3-SAT formula is a long list of small conditions on true-or-false variables, three variables per condition, and the question is whether some assignment satisfies all of them at once. Researchers have used the hypothesis for decades as a working assumption: OpenAI’s page says it has been used in hundreds of papers to derive hardness results in graph theory, databases, computational geometry and computational biology.
The manuscript, titled “The Exponential Time Hypothesis is False” and credited to “OpenAI”, is dated 17 October and revised 25 October 2026. It describes a deterministic algorithm that counts exactly how many assignments satisfy any k-CNF formula (the general version with k variables per condition, for any fixed k of at least 2). The running time grows like 2 to the power of n divided by roughly the square root of log n, with polynomial memory. Counting is at least as hard as deciding whether one solution exists, so if the algorithm and its analysis are correct, the hypothesis is false.
OpenAI’s page puts it this way: “our system has recently proved that the ETH is false, a result that was subsequently verified in Lean.” It dates the steps: the AI found its natural-language argument on 16 October and the team formalised it in Lean, a program that checks mathematical reasoning line by line, on 17 October. The page also warns that turning this into faster algorithms in practice “will require significant further research”.
The authors draw the limits themselves. Running-time bounds of this kind do not survive general polynomial-time reductions, they write, “so our result does not imply that general NP problems admit subexponential time algorithms”. There is no polynomial-time algorithm here, and the P versus NP question stays open. What does follow, according to the paper, is faster-than-exponential counting for a few graph problems such as independent sets, proper colourings and perfect matchings.
Who is checking it, and what the Lean check covers
The work “will be verified and shepherded”, according to OpenAI, by a group led by Impagliazzo, Paturi and Williams. Impagliazzo and Paturi, with Francis Zane, are the original proposers of the hypothesis. OpenAI notes that Williams has refuted strong versions of it. In their open letter to colleagues, the three write that “a result of this significance requires careful, independent scrutiny”. They ask the theoretical computer science community to help examine the argument, propose a virtual meeting before the end of 2026, and list a community repository, a response form and a discussion blog as places to contribute.
They also write that “if the claim is correct, it will change an important part of theoretical computer science.” The letter says nothing about cryptography. OpenAI says it agreed to the group’s requests to make all raw data public and to fund a conference on the implications.
The Lean check is narrower than the headline bound. OpenAI’s scope note says Lean proves a slightly weaker running time, with (log log n) squared in the exponent instead of log log n, and that the sharper figure comes from the 25 October manuscript. The weaker bound is still below exponential, so if the Lean statement faithfully captures the hypothesis and the algorithm, the machine-checked part alone would be enough to contradict it. Whether it does is one of the things reviewers have not yet said.
| Statement | Running time (n variables) | Where it comes from |
|---|---|---|
| Exponential Time Hypothesis (the conjecture) | 3-SAT needs at least 2cn in the worst case, for some constant c > 0 | Impagliazzo and Paturi, 1999 |
| OpenAI manuscript, any k-CNF formula | 2O(n log log n / √log n) | Paper, Theorem 1.1 (25 October) |
| OpenAI manuscript, sparse formulas | 2O(n / √log n) | Paper, Theorem 1.1 |
| Lean-checked statement | 2O(n (log log n)² / √log n) | OpenAI Lean scope note |
| Anthropic repository, #3-SAT counting | 2O(n log log n / √log n) | Anthropic formal-math README |
The constants hidden inside each O(…) are not given. Without them, nobody can say from these formulas at what size, if any, the method would beat the plain search that tries every assignment.
Anthropic published a similar result
Anthropic, the maker of Claude, published a paper titled “A 2^o(n) Time Algorithm for 3-SAT”, credited to “Claude (Anthropic)”, in its public formal-math repository; Decrypt reported that the paper is dated 26 October, the day of OpenAI’s announcement. The README says the algorithm counts 3-SAT solutions with the same kind of bound, that the result was found by an internal research Claude model, and that the Lean proofs depend only on Lean’s three standard axioms. It adds a caveat of its own: Lean checks the proofs, but no machine checks that the statement file says what the paper says. It also states: “The result is purely asymptotic and says nothing about solving formulas in practice.”
What complexity theorists said first
The complexity theorist Scott Aaronson wrote on his Shtetl-Optimized blog on 26 October that an OpenAI model “has now refuted the Exponential Time Hypothesis”, with a 3-SAT running time that scales roughly like exp(n/√log(n)). In the comments he raised his personal probability that P equals NP “from 3% to 5%” and summed up the gap that remains: “a foot-high fence has been breached, while a fence the height of the Empire State Building is still standing.”
He also stressed that the result is about k-SAT only, writing that “we still don’t have anything really better than brute force for CircuitSAT or FormulaSAT”, the more general problems. Asked by a reader on 27 October whether he had news of AI companies’ attempts to break cryptographic algorithms, he answered: “I have zero news about breaking of cryptographic codes.”
Why SHA-256 and bitcoin signatures are different problems
The fear in crypto threads ran like this: if an AI can make a famous hard problem easier, bitcoin’s cryptography could be next. That reasoning skips at least four steps.
First, the hypothesis is about growth. It describes how the worst-case cost of 3-SAT behaves as the number of variables goes to infinity. It says nothing about any single formula of fixed size. Bitcoin’s primitives are fixed objects: SHA-256 takes 512-bit blocks and returns a 256-bit output, and bitcoin’s signature keys live on one specific curve, secp256k1. A statement about what happens as n grows without limit does not, by itself, change the cost of attacking one fixed function.
Second, the gain in the exponent is small and grows very slowly. Compared with 2 to the power of n, the exponent shrinks by a factor of roughly the square root of log n, a quantity that barely moves: it goes from about 3 to about 4 when n grows from ten thousand to ten million variables. With the constants unpublished, the paper gives no running time for any real formula, no implementation and no benchmark.
Third, translation costs. A SHA-256 preimage search can in principle be written as a SAT formula, but every intermediate bit of the hash computation becomes a variable, so the formula has many thousands of variables, far more than the 256 output bits. The new bound is measured in the formula’s variables, not in the bits of the secret. The paper makes the general point itself: running-time bounds of this form “do not transfer under general polynomial-time reductions”, because an encoding that inflates the number of variables can wipe out a gain this thin. It does not discuss SHA-256 at all. For context on the basic building blocks, see our guide to what cryptography is and how it protects crypto.
Fourth, bitcoin signatures rest on a different problem. ECDSA and Schnorr signatures on secp256k1 depend on the elliptic-curve discrete logarithm problem: recovering a private key from a public key in a group of about 2256 elements. That is an algebraic problem, and the best known classical attacks on it take around 2128 operations. Like almost any problem whose answer can be checked, it could in principle be rewritten as a SAT formula, but the elliptic-curve arithmetic would turn a 256-bit key into a formula with vastly more variables, and the reduction caveat above applies again. The manuscript contains no discrete-log, elliptic-curve or hash-function content. Our explainer on how private and public keys work covers the link between the two.
Mining is a separate case again. Miners are not asked to invert SHA-256 for a given output; they compute it over and over, searching for a block header whose hash falls below a target that the network adjusts every 2,016 blocks. The same mix-up between hashes and signatures was at the centre of an earlier scare, which we covered when Chamath Palihapitiya’s ‘bitcoin goes to zero’ AI scenario confused the two on 24 October.
The one passage on inversion, and the limit it sets itself
The manuscript touches cryptography in exactly one place, Appendix C.2 on pages 52 and 53. Corollary C.2 deals with Boolean functions in which each output bit depends on only a constant number of input bits, a property called constant output locality. For such functions, the paper says, the number of inputs that map to a given output can be counted, and one such input found, in the same below-exponential time.
It then names one family it covers: constant-locality versions of candidate one-way functions proposed by Oded Goldreich in 2000, a research construction studied by theorists. For those, the paper says, its result rules out inversion hardness of the form 2 to a constant times n. The next sentence draws the line: “This does not rule out one-wayness against polynomial-time algorithms.”
SHA-256 is not in that family. Each output bit of SHA-256 depends on many input bits after its rounds of mixing, not on a fixed handful. So even where the paper speaks about inverting functions, it concerns a theoretical class built on purpose to be local, and the authors spell out the limit in the next breath.
What a real threat to bitcoin would have to show
A credible claim against bitcoin’s cryptography would need more than a new asymptotic bound. It would have to give an explicit encoding of a SHA-256 preimage search or of a secp256k1 discrete logarithm, the constants of the algorithm, working code, and a cost estimate that beats 2256 generic operations for preimages or 2128 for discrete logs. None of that has been published by OpenAI, by Anthropic or by anyone reviewing their papers.
The serious long-term question for bitcoin signatures remains quantum computing, where Shor’s algorithm would, on a large enough machine, solve the elliptic-curve discrete logarithm problem. That is a different matter with its own research path, which we followed when Google cut quantum magic-state errors 40-fold earlier this month.
We found no market move or regulatory statement tied to the claim. No statement from Bitcoin Core developers was found as of 28 October, and the reviewers’ letter does not mention cryptography.
What is still open, and the next dates
Whether the argument is correct is the first question, and it is unanswered: no independent reviewer had published a verdict by the morning of 28 October. The second is whether the Lean statement matches the paper’s claim. The third is how the OpenAI and Anthropic results relate, since both arrived within days and describe the same kind of bound; we found no explanation of the overlap from either company.
The reviewers’ proposed virtual meeting, planned before the end of 2026, is the next date to watch. Before then, the useful signals would be a published review from the community repository, a statement on the Lean formalisation from someone outside OpenAI, or an encoding and benchmark that put a number on any cryptographic use of the claimed refutation of the Exponential Time Hypothesis. None of the three had appeared by the morning of 28 October.