The claim concerns the Exponential Time Hypothesis. Independent scrutiny is open, and a practical Bitcoin attack would require several further steps.

OpenAI says its AI system has refuted the Exponential Time Hypothesis, a longstanding assumption about how difficult certain logic problems are to solve. The Oct. 26 announcement has researchers organizing an independent examination. The disclosed result does not establish a practical attack on Bitcoin.

ETH here means Exponential Time Hypothesis, rather than Ether. The subject is 3-SAT, a puzzle in which a computer must find true-or-false settings that satisfy a collection of logical rules. The hypothesis says solving these problems requires exponential time in the number of variables in the worst case.

OpenAI says the result was verified in Lean, a proof assistant, although its scope note describes a weaker time bound than the manuscript's sharpest claim. The researchers organizing the community's examination have expressly declined to certify it. Their letter says, “Our involvement should not be taken as certification of the claim.”

The manuscript, dated Oct. 17 and revised Oct. 25, claims a deterministic algorithm that exactly counts the satisfying assignments of fixed-width Boolean formulas in subexponential time and polynomial space. In plain English, its running time grows more slowly than an exponential bound as the problem gets larger. That is a different promise from making the problem easy on today's computers.

The disclosed bound does not establish a polynomial-time algorithm or settle P=NP, the question of whether every decision problem whose proposed solutions can be verified in polynomial time can also be solved in polynomial time.

Source link