OpenAI model allegedly disproves exponential time hypothesis
An internal OpenAI model found an algorithm solving 3SAT faster than the exponential time hypothesis allows. The proof, checked in Lean, invalidates previous hardness results in theoretical computer science.
OpenAI announced that an internal model has found an algorithm that solves 3SAT puzzles faster than the exponential time hypothesis (ETH) allows, effectively disproving the hypothesis. The proof has been checked in Lean, a computer verification system. The ETH, proposed about 25 years ago by Russell Impaglione, Rohamo Patry, and Francis Zane, posited that no algorithm could solve 3SAT without exponential time complexity. This hypothesis served as a foundational assumption for hundreds of papers in scheduling, graphs, and logic.
If the disproof is accurate, a significant portion of theoretical computer science must be revisited. The original proposers, along with MIT's Ryan Williams, are leading the public review of the proof. Greg Brockman tweeted about the solution. The new algorithm is still slow in absolute terms and does not solve the P versus NP problem, but it invalidates previous hardness results based on ETH. The development is described as a major breakthrough that requires redrawing the map of what is computationally possible.