Frontier AI Labs Claim Their Models Refuted the Exponential Time Hypothesis—Here's What That Actually Means
OpenAI released solutions to three major mathematical problems that have long challenged researchers. One was a surprise rejection of the Exponential Time Hypothesis (ETH)—a durable assumption in computer science that plays a central role in how we understand what is difficult to compute.
As with previous proof-drops from the frontier lab, the scientific community responded with a mixture of excitement and dismay. Anthropic mathematician Levent Alpöge suggested that OpenAI's solutions were based on pre-existing work, and hours later, Anthropic released its own refutation of ETH.
OpenAI's process, however, is evolving. This time, the lab structured its releases differently for each of the three disciplines involved: mathematicians received the work via GitHub; computer scientists formed a working group and asked for the proofs to be shared publicly, with OpenAI funding a conference to discuss them; and physicists formed a working group that will determine how their result is released.
A Community Responds
MIT Professor Ryan Williams, a computer scientist who focuses on computational complexity, is organizing his field's response to the new finding. Williams has criticized OpenAI's approach in the past, calling an earlier proof dump in October a "DDoS attack on mathematicians."
Nevertheless, he agreed to collaborate with the frontier labs to help shepherd ideas that are vital to the field, he told TechCrunch. The lab asked him to help interpret the solution, alongside UC San Diego computer scientists Russell Impagliazzo and Ramamohan Paturi, who first published the ETH in 1999.
Their first step was to release an open letter calling for feedback from scientists interested in these problems and inviting discussion of the norms around AI contributions to their work.
"Some parts [of OpenAI's proof] are, maybe you could say, routine, but then yes, there are two or three alien-looking parts, and it's exactly these parts that I saw that made me think, wow, this is something that the whole community needs to work on together," Williams told TechCrunch.
Are You Down with P vs NP?
The ETH is part of a broader class of problems known as P vs NP, which has animated computer science and many other fields for decades. Put reductively, researchers are trying to understand whether any problem whose solution can be easily verified (NP) can also be easily solved (P).
A simple example is the game Sudoku: once a solution to a puzzle is in place, it can be quickly verified, but finding the solution is time-consuming. That dynamic holds true across a range of important problems, and the insight underpins cryptographic systems: when you have the key to an encoded message, you can reveal it, but actually cracking an effective cipher takes too long to be useful.
However, scientists have yet to prove whether that is always true. "P = NP is saying that, not only can you verify Sudoku solutions when they exist, you can just generate them," Williams said. "P = NP is asserting that this is true for every single problem you can verify quickly—if you can verify it quickly, you can solve it quickly. So this just seems too good to be true."
That's why most scientists assume that P ≠ NP. ETH provided evidence for that assumption—until now.
via TechCrunch AI