OpenAI released solutions to three long-standing mathematics problems yesterday, including a rejection of the Exponential Time Hypothesis. This finding challenges a durable assumption in computer science regarding what is difficult to compute.
Scientific communities reacted with a mixture of excitement and concern. Levent Alpöge, a mathematician at Anthropic, suggested OpenAI had based its solutions on pre-existing work. Hours later, Anthropic released its own refutation of the hypothesis.
OpenAI changed its release strategy this time. It split the work across three disciplines: mathematicians received the files directly on GitHub; computer scientists formed a working group to share proofs publicly and discussed funding a conference; physicists formed a separate working group to decide on their release method.
Ryan Williams, a professor at MIT and computer scientist specialising in computational complexity, is organising the field’s response. Williams has previously criticised OpenAI’s approach, calling an earlier proof drop a “DDOS attack on mathematicians.” He agreed to collaborate with the lab to shepherd vital ideas, telling TechCrunch he would 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 releasing an open letter calling for feedback from scientists interested in these problems and a discussion of 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 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. Researchers are trying to understand if any problem whose solution can be easily verified can also be easily solved.
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 is true across a range of important problems and underpins cryptographic systems. When you have the key to an encoded message, you can reveal it, but actually cracking an effective code 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 that just seems too good to be true.”
That is why most scientists assume that P ≠ NP. ETH provided evidence for that. It basically says that even the fastest computer algorithm needs exponentially more time to find a solution as the number of variables grow in a specific class of tricky logic puzzle.
The claims from OpenAI and Anthropic is that their models have come up with algorithms that solve those puzzles in “sub-exponential” time, meaning faster than the speeds previously thought possible. If true, they may have proven the EFT to be false and maybe opened up a path for algorithms that generally perform P = NP.
“Every computer scientist should probably put a a little more weight on the plausibility of P = NP, but one’s weight may vary,” Williams said. “I do think that it kind of calls into question a lot of the intuitions that we thought we had about … how tractable [hard NP problems] are. I also think that this is probably not the final answer either. I don’t think that OpenAI’s algorithm could possibly be the best algorithm you can get.”
The work ahead for computer scientists
The durability of ETH has lead to it being included in many scientific papers over the past decade that will need to be revisited if the AI labs claims that they’ve proven it wrong holds up, Williams said.
“This is partly why I was asking or pushing OpenAI to support a conference on this — it’s going to affect many researchers’ works, and we need to figure out, okay, what happens next besides understanding the algorithms, we need to understand, what should the foundations be that we had before?” he said.
Before scientific concerns, there are cybersecurity questions. Williams said that an improved algorithm could imply that cryptographic systems relying on certain key sizes could be considered broken. So one of the first questions he asked OpenAI science lead Dan Roberts was if they had checked that that this affects any crypto systems … is anything insecure now? And apparently, they checked, and they were reasonably confident that this didn’t … imply any breaks.
This new AI paradigm of scientific discovery is still a work in progress, but Williams says he is optimistic despite real concerns, particularly about training the next generation of scientists. Being a computer scientist who does high level math has perhaps made the adjustment easier for him than for pure mathematicians.
Still, he says AI is “forcing people to be a little more ambitious about the kind of work that they do, and to think more deeply about okay, if all the things I used to work on are now low hanging fruit for AI, how can I raise the bar for the the kind of scientific questions I want to ask?”
