The Exponential Time Refutation

In this week's big news (though it's only Wednesday), OpenAI announced a proof that the exponential-time hypothesis is false, with a Lean proof. Later Anthropic released their own paper. Ryan O'Donnell and Shiva Kintali posted follow-up proofs, smartly focusing on simplicity rather than getting the best bounds. OpenAI will partner with three of my favorite complexity theorists, Russell Impagliazzo, Mohan Paturi and Ryan Williams to verify and study the proof. I have not verified the proof myself, but it is safe to assume now that the exponential-time hypothesis is toast. Recall 3-SAT, the problem of determining whether a Boolean formula that is an AND of ORs of three variables or their negations has a satisfying assignment. 3-SAT is the prototypical NP-complete problem from which we derive all the others. The exponential-time hypothesis (ETH), introduced by Impagliazzo and Paturi in 1999, building on their work with Francis Zane, states that there is a \(c > 0\) such that every…