Computer Science and Complexity Theory
In computer science, OpenAI claims its AI disproved the Exponential Time Hypothesis (ETH), a longstanding conjecture regarding the computational difficulty of solving certain problems. The company stated that the ETH has been "widely believed to be true" and used in hundreds of papers to derive conditional computational hardness results.
Ryan Williams, an expert in computational complexity theory at MIT, said a confirmed refutation would be a major development. "We are working to verify and examine their proof and determine if it holds up," Williams told Al Jazeera. He added that the proof proposes a "mysterious new method to more efficiently solve a variety of fundamental problems."
OpenAI has published the AI-generated explanation and the formal proof in Lean on GitHub. The work is being examined by a group including Russell Impagliazzo, Ramamohan Paturi, and Ryan Williams.