Submission + - OpenAI claims Exponential Time Hypothesis false, long though likely true
The computer science collaboration will understand and explain a result concerning the Exponential Time Hypothesis (ETH), a longstanding conjecture about the computational complexity of Boolean formula satisfiability, a problem deeply related to the P vs. NP problem. The ETH has been widely believed to be true, and has been used in hundreds of papers to derive conditional computational hardness results across a wide variety of fields including graph theory, computational biology, databases, computational geometry, and more. Surprisingly, our system has recently proved that the ETH is false, a result that was subsequently verified in Lean. The refutation of the ETH reopens questions about how much faster these tasks could become, and may help guide the search for better algorithms. Finding such algorithms, and turning theoretical advances into practical improvements, will require significant further research.
Other coverage and discussion, some of which may be paywalled or login-required now or soon:
- New York Times November 6 How A.I. Just Blew Up a Key Tenet of Computer Science
- Reddit The Exponential Time Hypothesis is false
- MindStudio AI Just Disproved the Exponential Time Hypothesis. Here's Why It Matters: OpenAI says its AI disproved a 27-year-old computer science belief, the exponential time hypothesis, in 10 days. Here's what that means.
- HackerNews Efficient algorithms, the Exponential Time Hypothesis, and losing the plot
Related academic work cited in New York Times article, subscription required: Which problems have strongly exponential complexity?, from 1998