OpenAI claims AI breakthrough, but Bitcoin attack remains unproven
OpenAI says its AI system refuted the Exponential Time Hypothesis. Researchers will review the claim, which does not show a practical attack on Bitcoin mining or signatures.
OpenAI claims its AI system has refuted the Exponential Time Hypothesis, a long-standing assumption that certain logic problems require exponential computing time in the worst case. The claim has prompted researchers to organize an independent examination.
The announcement came on Oct. 26, after researchers presented a manuscript dated Oct. 17 and revised on Oct. 25. The paper describes a deterministic algorithm that exactly counts solutions to fixed-width Boolean formulas in subexponential time while using polynomial space.
The work concerns 3-SAT, a problem in which a computer must assign true or false values to variables so that a set of logical rules is satisfied. The hypothesis holds that solving such problems requires exponential time in the number of variables. A subexponential result means the running time grows more slowly than an exponential function as the input becomes larger.
OpenAI reported that the result was formalized in Lean, a proof assistant used to check mathematical arguments. The scope of the Lean formalization, however, covers a weaker subexponential bound than the manuscript’s sharpest claim. The result does not provide a polynomial-time algorithm or resolve the P-versus-NP problem.
Ryan Williams, Russell Impagliazzo and Mohan Paturi have been asked to organize an open examination of the claim. Williams described the review as proceeding without nondisclosure agreements or compensation. The organizers wrote that their involvement “should not be taken as certification of the claim.”
The available review has covered the introductory pages of the paper, rather than the full proof. No attack times, encoding sizes or performance benchmarks have been established, and no independent cryptographic audit has been completed.
The connection to Bitcoin remains theoretical. Miners search for block-header hashes below a network-set target, while users authorize transactions with digital signatures. Bitcoin recalculates its mining difficulty every 2,016 blocks. That adjustment concerns block production and does not address the security of transaction signatures.
Bitcoin uses ECDSA and Schnorr signatures with the secp256k1 elliptic curve. An attack would need to recover a private key from a public key or defeat the relevant elliptic-curve and hash-function assumptions. A faster method for solving general SAT problems does not by itself provide such a method.
A practical attack would require a suitable encoding of a specific mining or signature problem, an implementation of the claimed algorithm and evidence that its cost is lower than existing methods. The number of variables in a SAT formula cannot be directly treated as the bit length of a Bitcoin key or hash.
In a separate post, Williams wrote that OpenAI had apparently checked whether existing cryptosystems were compromised and found no immediate issue. That account was second-hand and was not an independent audit. OpenAI has indicated that practical improvements based on the result would require significant further research.








