OpenAI claims cryptography breakthrough refuting Exponential Time Hypothesis, Bitcoin attack unestablished

The claim specifically addresses 3-SAT, a problem where a computer must find true-or-false settings satisfying logical rules. The ETH posits that solving these problems requires exponential time in the worst case relative to the number of variables.

OpenAI states its AI system refuted this hypothesis. The manuscript, revised on Oct. 25 and dated Oct. 17, claims a deterministic algorithm that counts satisfying assignments for fixed-width Boolean formulas in subexponential time and polynomial space.

However, this disclosed bound does not establish a polynomial-time algorithm nor does it settle P=NP. The researchers overseeing the community examination have explicitly stated, "Our involvement should not be taken as certification of the claim."

The purported ETH refutation pertains to formula solving, which differs from the concrete tasks involved in Bitcoin mining or spending. A theoretical SAT speed-up alone does not establish a measurable mining advantage.

Bitcoin's processes, such as mining for a block-header hash or authorizing spending via signatures, are distinct cryptographic functions. The SAT claim does not demonstrate the ability to recover a secp256k1 private key.

The independent examination is currently limited to the introductory pages 1–8 of the paper. No benchmarks, encoding sizes, attack times, or independent cryptographic audit have been established.

This development enters a broader context where market participants and institutions are closely monitoring theoretical advances against established protocol security. OpenAI itself maintains that realizing practical improvements necessitates considerable additional research.