OpenAI Says AI Refuted the Exponential Time Hypothesis, MIT Professor: This Isn't the Final Answer

Image Credits: ChatGPT

OpenAI has once again dropped three bombshells on the academic community. This time, they are three long-standing unsolved math problems, one of which hits the very foundation of computer science: the Exponential Time Hypothesis (ETH).

The scientific community is both excited and uneasy. Anthropic mathematician Levent Alpöge hinted on X that OpenAI's solutions build on existing work. A few hours later, Anthropic also published its own refutation of ETH.

OpenAI's process has changed. Three disciplines, three different treatments: for mathematicians, they just dumped the work on GitHub; for computer scientists, they formed a working group, required the proof to be shared publicly, and OpenAI had to foot the bill for a conference; for physicists, they set up a working group to decide how to publish. It looks like OpenAI is learning to engage with each academic discipline.

MIT professor Ryan Williams is organizing the computer science community's response. He had previously criticized OpenAI, calling their approach a “DDOS attack on mathematicians.” This time he agreed to collaborate because these ideas are too important to the field. OpenAI invited Williams, along with Russell Impagliazzo and Ramamohan Paturi, who proposed ETH in 1999, to help interpret the findings. They first sent out an open letter soliciting feedback.

Williams said that most of the content in OpenAI's proofs “could be described as routine,” but two or three parts look like “alien artifacts.” It is precisely these parts that made him realize the whole academic community needs to tackle them together.

To understand this, you need to go back to P and NP.

NP problems are easy to verify but hard to solve. Sudoku is a typical example: a completed Sudoku grid is quick to check, but filling it in yourself could take a lifetime. P=NP would mean that every problem that is quick to verify is also quick to solve. That sounds too good to be true. So most scientists believe P≠NP.

ETH provides supporting evidence for P≠NP. It says that for a specific class of logical problems, even with the fastest algorithm, the solving time grows exponentially as the number of variables increases.

OpenAI and Anthropic claim that their models have proposed “sub-exponential time” algorithms—faster than exponential time. If this holds, ETH is overturned. The further implication is that P=NP may not be so far away.

Williams said every computer scientist should give a little more weight to the possibility of P=NP, but how much is up to each individual to decide. He acknowledged that this discovery shakes many intuitions about “which problems count as hard.” But he doesn't think this is the final answer: “OpenAI's algorithm can't possibly be the best algorithm you can get.”

The impact is real. Over the past decade, numerous papers have used ETH as a background assumption. If ETH falls, that research needs to be revisited. Williams pushed OpenAI to fund a conference specifically to figure out “what to do next.”

Before discussing the academic impact, we first need to answer the security question. Faster algorithms could mean that cryptographic systems with certain key lengths are no longer secure. The first thing Williams asked OpenAI's head of science, Dan Roberts, was: “Have you checked the impact on existing cryptographic systems? Is anything insecure right now?” Roberts said he checked and found no vulnerabilities that could cause real-world damage.

How AI participates in scientific discovery is still being worked out. Williams said AI is “forcing people to be more ambitious in their work.” If what scientists used to research is all low-hanging fruit for AI, then scientists need to think about how to raise the bar.

Before, AI helped people find answers. Now, AI is forcing people to change the questions.