- OpenAI says an AI system of its own produced a result refuting the Exponential Time Hypothesis, a 1999 conjecture about how long hard logic problems take to solve. The claim is OpenAI’s, reported via its announcement and a manuscript on its GitHub, and has not been independently certified.
- Three complexity theorists were asked to organise open scrutiny. Their letter says plainly that taking part is not an endorsement.
- No encoding, benchmark or demonstrated attack connects any of this to Bitcoin or to the signatures that protect your coins.
A maths claim from an AI lab landed on 26 October and within a day it was being discussed as a question about whether Bitcoin still works. The two are much further apart than the headlines suggest, and the distance between them is worth understanding properly, because this will happen again.
Every so often a story arrives that sounds like it might make your crypto worthless. Most of them are a technical result being stretched a very long way by people who have not read it. Knowing roughly where the real line sits, between a theoretical speed-up and an actual way of taking someone’s coins, means you can read the next one of these without the spike of panic. There is nothing here that changes what a Bitcoin holder should do today.
What OpenAI actually said
On 26 October, OpenAI published a post about working with academic communities. Inside it was a claim that one of its systems produced a result refuting the Exponential Time Hypothesis.
A manuscript on OpenAI’s GitHub maths repository, dated 17 October and revised 25 October, sets out a deterministic algorithm that exactly counts the satisfying assignments of fixed-width Boolean formulas in subexponential time and polynomial space. That sentence contains about four ideas that need unpacking, so take them one at a time.
SAT, in plain terms
A Boolean formula is a logic puzzle. You have a list of true-or-false variables and a set of conditions they have to satisfy, each condition written as “this OR that OR the other”. The question is whether any combination of true and false settings makes every condition hold at once. That question is called SAT, short for satisfiability. When each condition involves exactly three variables, it is 3-SAT.
3-SAT is the standard example of a problem that is easy to check and apparently hard to solve. Hand someone a proposed answer and they can verify it in seconds. Ask them to find one from scratch and, as far as anyone knows, the work grows roughly exponentially with the number of variables: add one variable and you can roughly double the search.
The Exponential Time Hypothesis, proposed by Russell Impagliazzo and Ramamohan Paturi in 1999, is the formal version of “as far as anyone knows”. It conjectures that 3-SAT genuinely requires time exponential in the number of variables, with no clever trick available to escape that. A great deal of modern complexity theory is built assuming it holds. Refuting it would be a significant piece of mathematics.
Subexponential is not fast
This is where the gap between the result and the panic opens up.
“Subexponential” means slower-growing than exponential. It does not mean quick. An algorithm can be subexponential and still take longer than the age of the universe on a problem of realistic size. The word that would matter is “polynomial”, meaning the work grows at a manageable rate, and the disclosed bound is not polynomial. By CryptoSlate’s reading of the manuscript’s opening pages, the result does not produce a polynomial-time algorithm for 3-SAT and does not settle P versus NP, the open question about whether problems that are easy to check are also easy to solve.
So even taken entirely at face value, this is a result about where a boundary sits in theory. It is not a machine that solves hard problems quickly.
What is not yet established
OpenAI asked three complexity theorists, Impagliazzo, Paturi and Ryan Williams, to organise an open examination of the claim. No NDAs, no payment. Their letter is unusually blunt about what their participation means:
“Our involvement should not be taken as certification of the claim.”
That examination is ongoing. CryptoSlate’s own account notes that the available public scrutiny, including its own, covers the manuscript’s introductory pages 1 to 8 rather than the complete proof. There is also a mismatch inside OpenAI’s own repository: its Lean formalisation scope note, Lean being a system for machine-checking mathematical proofs line by line, describes a weaker time bound than the manuscript’s sharpest claim. The strongest version of the claim is the part that has not been machine-verified.
Williams separately posted on X that he asked OpenAI whether existing cryptosystems were compromised, and that OpenAI relayed they were apparently safe. That is a second-hand account of an internal check on social media, not an audit, and what was tested is not public.
What would actually have to break
Bitcoin leans on two separate pieces of mathematics, and neither of them is 3-SAT.
Mining is a hashing contest. Computers repeatedly run a block header through SHA-256 and hope the output lands below a target number. There is no structure to exploit and no shortcut known: you try, you fail, you try again, billions of times a second. Breaking that would mean finding a way to run SHA-256 backwards, which is a problem about hash functions, not about logic formulas.
Spending is protected by elliptic curve cryptography. Your is a number, your public address derives from it, and the security rests on the discrete logarithm problem over the curve secp256k1 being infeasible to reverse. That is what ECDSA and Schnorr signatures, the two schemes Bitcoin uses, depend on. Breaking it would mean recovering a private key from a public one.
You can, in principle, translate hashing or key recovery into a giant SAT instance. Cryptographers have done it for years as a research exercise. The formulas that come out are enormous, and nobody has published an encoding showing how the number of variables in such an instance relates to a 256-bit key, let alone a cost comparison against simply guessing. No measured mining advantage, no recovered key, no runtime figures. Our inference, and we label it as one: until somebody produces that bridge with numbers attached, the connection between this result and Bitcoin is an assumption rather than a finding.
The quantum worry, same week
Running alongside this was a familiar argument that quantum computing is already affecting how large investors treat Bitcoin. Stacks co-founder Muneeb Ali has said quantum uncertainty is deterring institutional money.
Worth separating the two halves of that. The underlying technical concern is real and well understood: a sufficiently large, error-corrected quantum computer running Shor’s algorithm would break elliptic curve signatures, which is why post-quantum signature schemes are an active area of Bitcoin development. The claim about institutional behaviour is a different kind of statement. It is an assessment from someone in the industry, not a survey of allocators, and no public dataset separates quantum concern from the dozen other reasons a fund does or does not buy. Report it as a view held by a named person and leave it there.
What to watch
Three things will tell you more than any amount of commentary. Whether the independent examination reaches a conclusion, and what it says about the sharpest claimed bound rather than the weaker verified one. Whether the Lean formalisation is extended to cover the full result. And whether anyone, at any institution, publishes an explicit encoding from this algorithm to SHA-256 or secp256k1 with timing figures.
Until that third thing exists, the correct description of this story is a contested mathematics result that has not been connected to cryptography by anyone, including its authors. If it ever is, that will be a much louder story than this one, and it will arrive with numbers in it. For the background on how key ownership actually works, our guide to self-custody covers the mechanics, and Bitcoin coverage sits in technology.