OpenAI says AI refutes 27-year-old Exponential Time Hypothesis

OpenAI says an AI model has disproved the Exponential Time Hypothesis (ETH), challenging an assumption that researchers relied on for 27 years. The model developed a faster algorithm for the 3-SAT logic problem. OpenAI's system generated a natural-language proof on October 16. The team translated the proof into Lean the following day, allowing software to check each logical step.

The published algorithm takes roughly 2^(n/√log n) steps for an input containing n variables. That running time undercuts the exponential lower bound predicted by ETH but remains too slow for practical applications. OpenAI cautions that substantial additional research is necessary to achieve practical speed improvements. Russell Impagliazzo and Ramamohan Paturi of UC San Diego will lead the review with MIT's Ryan Williams. OpenAI is not claiming scientific credit for the discovery, following an earlier dispute involving Navier-Stokes.

Impagliazzo and Paturi introduced ETH in 1999. The hypothesis concerns 3-SAT, which asks whether true-or-false values can be assigned to variables while satisfying every linked condition. A proposed solution is easy to verify, but each additional variable doubles the number of possible combinations to search. ETH asserts that no algorithm can avoid exponential growth in the worst case. OpenAI says hundreds of papers used the hypothesis to establish computational difficulty in graph theory, computational biology and databases. The acronym ETH has no connection to Ethereum's ticker.

The result does not establish that P equals NP. The P versus NP question asks whether all problems whose solutions can be checked quickly can also be solved quickly. ETH made a stronger assertion than P ≠ NP, so refuting ETH does not settle that broader question. OpenAI president and co-founder Greg Brockman emphasized that distinction hours after the announcement. The algorithm does not directly threaten the cryptography protecting Bitcoin or Ethereum. Bitcoin signatures use elliptic curve cryptography, and the algorithm does not solve the mathematical problem underlying that system.

Scott Aaronson, a computer science professor at the University of Texas at Austin, said students brought Aaronson news of the claimed refutation. Earlier mathematical breakthroughs also overturned assumptions about computational limits. Anatoly Karatsuba refuted Andrey Kolmogorov's multiplication conjecture in about a week in 1960. Volker Strassen sought to establish the optimality of standard matrix multiplication in 1969 but instead discovered a faster approach. Machines now generate proofs that humans then work to understand. The same release also claimed additional proofs involving harmonic analysis and particle physics.

Cryptographer Matthew Green has warned that AI could undermine the mathematics protecting wallets. Benjamin Cowen, a member of BeInCrypto's Market Intelligence Expert Council, argued that developments in disciplines distant from finance can eventually change markets. AI advances increasingly test the computational difficulty assumptions on which digital assets depend.