Contested ETH: OpenAI and Anthropic, the Community Organizes

Two AI laboratories claim to have found algorithms that could circumvent the Exponential Time Hypothesis (ETH). The computer science community is mobilizing to verify these results, assess their potential implications for cryptography, and, if necessary, rewrite a decade of literature.

Article Revisions Considered and Initial Security Check

The Exponential Time Hypothesis (ETH) has been used in numerous scientific papers over the past decade. Ryan Williams believes that this work will need to be reexamined if the claims from the AI laboratories are confirmed. He has encouraged OpenAI to support a dedicated conference, as these results could be relevant to many researchers. Even before a complete scientific review, Williams questioned Dan Roberts, OpenAI's chief scientist, about potential impacts on cryptography. According to Williams, OpenAI has verified and is reasonably confident that the results do not imply vulnerabilities in cryptographic systems. However, Williams emphasizes that an improved algorithm could make certain key sizes vulnerable, necessitating ongoing vigilance.

Working Groups and Open Letter to Frame Collective Review

Computer scientists have formed a working group, requested the public release of evidence, and sought funding from OpenAI for a conference to discuss the findings. Physicists have also formed a group to determine how to publish their results, a process that is still ongoing. An open letter invites interested scientists to contribute and discuss the standards governing the role of AI in this research. Ryan Williams, a professor at MIT, is coordinating the field's response and working with Russell Impagliazzo and Ramamohan Paturi, who published the ETH in 1999.

Claims from the Laboratories and Initial Reactions

OpenAI has published solutions to three major mathematical problems, one of which would refute the Exponential Time Hypothesis, and has shared the mathematical work via GitHub. Levent Alpöge, a mathematician at Anthropic, suggested that OpenAI was relying on prior work before Anthropic subsequently published its own refutation of the ETH. Ryan Williams had criticized OpenAI's publication approach in October, calling it a "DDoS attack on mathematicians," but he is now collaborating with the Frontier laboratories to frame the interpretation of the results. He believes that while some parts of the proof are familiar, two or three passages seem foreign and require thorough examination by the community.

Theoretical Framework: P vs NP, ETH, and Sub-Exponential Promise

The debate is situated within the P vs NP question: Can problems for which a solution can be quickly verified also be solved quickly? Sudoku illustrates this difference between verification and search. The most widely held position assumes that P is different from NP. The Exponential Time Hypothesis asserts that for a class of logical puzzles, even the best algorithm sees its computation time grow exponentially with the number of variables. OpenAI and Anthropic claim to have found sub-exponential algorithms for these cases. If this performance is confirmed, it would invalidate the hypothesis and could, perhaps, pave the way for algorithms that generally achieve P = NP.

A Shift in Perspectives, No Final Verdict According to Ryan Williams

For Ryan Williams, the plausibility of P = NP should be given a bit more consideration, although this varies among researchers, and he believes that OpenAI's algorithm is probably not the best possible version. The AI paradigm for scientific discovery is still under development. Williams expresses optimism while voicing concerns about training the next generation of scientists. He notes that his experience as a computer scientist doing high-level mathematics facilitates his adaptation compared to more theoretical mathematicians. Finally, he believes that AI is pushing researchers to aim for more ambitious goals and to raise the scientific questions being asked.