OpenAI and Anthropic AI models challenge core computer science theory

OpenAI released solutions to three difficult math problems, including a surprise rejection of the Exponential Time Hypothesis, a key assumption in computer science. The move prompted a mixture of thrill and dismay from scientific communities, while Anthropic mathematician Levent Alpöge suggested OpenAI based its solutions on pre-existing work. Hours later, Anthropic released its own refutation of the same hypothesis. MIT Professor Ryan Williams is organizing his field's response to these findings. Williams previously criticized OpenAI's proof dump as a DDoS attack on mathematicians, but he agreed to collaborate with the frontier labs to help interpret the solution. He is joined by UC San Diego computer scientists Russell Impagliazzo and Ramamohan Paturi, who first published the hypothesis. The team released an open letter calling for feedback from scientists and a discussion on norms around AI contributions. Williams noted that the proof contains two or three alien-looking parts that require the whole community to work together.

Context

The Exponential Time Hypothesis relates to the broader P vs NP problem, which questions whether easily verifiable problems can also be easily solved. If AI models have indeed found sub-exponential algorithms, it could challenge long-held assumptions in computer science, though experts say cybersecurity systems appear safe for now.