OpenAI and Anthropic Claim to Disprove a Core Complexity Conjecture

If confirmed, the result would put a large body of published theoretical computer science work in question, though it leaves web security untouched.

OpenAI and Anthropic both said this week that they had disproved the exponential time hypothesis, a conjecture about how the difficulty of certain problems grows with their size. Large areas of theoretical computer science rest on that conjecture, so a confirmed result would put many published papers in question. The AI-generated proofs have not yet been independently checked, and OpenAI has enlisted the original proposers and an MIT researcher to help examine them. One UC Santa Barbara researcher estimates that about 50 of his papers would become pointless or need revisiting if the result holds, while others see new routes opened up by it. Cryptography designers are also watching, though the result does not directly touch the assumptions that underpin web security.