OpenAI says AI system refuted the Exponential Time Hypothesis

OpenAI says its AI system produced a result refuting ETH, which concerns the computational complexity of Boolean formula satisfiability, a problem related to P versus NP.[1] The company says the system found a natural-language disproof on October 16, 2026, then formalized it in Lean the next day.[1] OpenAI says the result was verified in Lean and that it released both the natural-language write-up and Lean proof in a public GitHub repository.[1] The company’s preprint is dated October 25, 2026.[2] The central claim is a theoretical result; OpenAI says substantial further work is needed to find algorithms and turn theoretical advances into practical improvements.[1]

ETH has been used in hundreds of papers to derive conditional computational hardness results.[1] OpenAI says the conjecture is relevant across graph theory, computational biology, databases and computational geometry.[1] That makes the result a reason for researchers to check which conclusions in their work depend on ETH, rather than assume that all such results have failed.[1][3] The distinction matters: a refutation of ETH does not by itself prove P equals NP, and the reported finding does not directly break existing cryptography.[3][5] The practical consequences will depend on further examination and research.[1]

OpenAI says the result will be examined by a group led by Russell Impagliazzo and Ramamohan Paturi of UC San Diego and Ryan Williams of MIT.[1] The company says the group asked for the underlying research materials to be made public and for OpenAI to fund a conference on the result’s implications.[1] OpenAI also says participants in its external collaborations are unpaid, act independently and retain ownership of their conclusions.[1] Separately, WIRED reported that researchers had not independently verified or fully understood the AI-generated proofs at the time of its report.[4] That distinction is important: Lean verification is reported, but independent review and understanding remain part of assessing what the result means.[1][4]