OpenAI and Anthropic each say their models have refuted the Exponential Time Hypothesis, a computer science assumption first published in 1999, TechCrunch reports. OpenAI released solutions to three long-standing maths problems, one of which rejects the hypothesis. Anthropic put its own refutation on GitHub hours later.
The claim is that the models found algorithms that solve the relevant puzzles in sub-exponential time. If it holds, it could open a path toward P = NP, though TechCrunch treats this as a claim and not an established result.
Levent Alpöge, an Anthropic mathematician, suggested on X that OpenAI’s solutions drew on existing work. The report does not say whether that has been checked.
Ryan Williams of MIT, who is organising the computer science response, called some parts of the proof routine and “two or three alien-looking parts” a reason for the field to work on it together. He thinks researchers should give P = NP “a little more weight”, and that the algorithm is probably not the final answer.
The hypothesis’s authors, Russell Impagliazzo and Ramamohan Paturi of UC San Diego, were asked by OpenAI to help interpret the work. Computer scientists have asked for proofs to be shared publicly and for OpenAI to fund a conference.
Williams also raised cryptography, since an improved algorithm could break some systems at certain key sizes. OpenAI checked and was, he relays, “reasonably confident” nothing broke. That is OpenAI’s own check.
The hypothesis appears in many papers from the past decade, which would need revisiting if the claims stand.
Whether either refutation survives scrutiny, and whether OpenAI’s was original, is not yet answered.
