I have been thinking for some time about how to write an article on the recent slew of results released by the big AI companies claiming to resolve many unsolved problems in mathematics. One of the challenges in doing this is that there are so many results (close to 400 in one release) in various subfields of math that I am ill-equipped to cover all of them in even a year’s worth of For Math’s Sake columns.
Nonetheless, these are still important things to write about in my view — not just because of the mathematical results, but of what AI’s role in them says about the field going forward. The effects of these developments may go well beyond reshaping what mathematics looks like in the future. I think the quintessential example of this is a recent claimed disproof of the Exponential Time Hypothesis (ETH), a conjecture in theoretical computer science about the complexity of certain types of computer algorithms.
I’ve just used a lot of jargon in that last sentence, so let me try to explain in more general terms what this is all about. First, the goal of algorithms is to solve problems with a computer. These problems can feature a number of variables, and the understanding is that the more variables you have, the harder the problem is to solve. Complexity theory seeks to quantify just how hard a problem is, by measuring the growth in time it takes for the algorithm to work as the number of variables increases. When this amount of time grows at an exponential rate, like two to the power of the number of variables, then we say the problem is solvable “in exponential time.” These are among the trickiest kinds of problems to deal with, because algorithms whose complexity grows exponentially quickly become unfeasible to implement on an actual computer.
ETH posited that a certain set of problems could not be solved in anything faster than exponential time. But OpenAI and Anthropic have independently claimed to disprove this hypothesis by announcing algorithms found by their AI models claiming to solve the set of problems. This has even made headlines because of the possibility that we may be able to solve other problems more quickly than previously thought, if only we can find the right algorithm to do it.
Ideally, we look for problems that can be solved “in polynomial time,” where the complexity only grows like the number of variables raised to a certain power. Additionally, there are problems that seem harder to solve but whose solutions are verifiable in polynomial time. A core problem of math and computer science is whether the problems in class P (solvable in polynomial time) fall into the same category as those in class NP (whose solutions can be verified in polynomial time). The negative result of the ETH means there may be an ever-so-slight possibility that P = NP, contrary to the consensus in the field.
I’m no expert in complexity theory, and I will emphasize that the P versus NP question is much more general than ETH, and thus remains (perhaps) far more difficult to resolve. Also, a result that P = NP could be rather dangerous — think about how encryption is based on the idea that the encrypted message is hard to decipher unless you know the key. If P = NP, one could in theory find an algorithm that can break this encryption in a similar amount of time as someone who already has the key.
But I think the point of all this is, for now, that AI companies continue to display the immense power of computation in solving problems for mathematics and computer science. This is great for the fields in some respects, but we should be immensely careful. While the contributions from computers can be polynomially, even exponentially valuable, human work and thought should remain priceless.
