OpenAI's AI Disproof of 1998 ETH Shocks Co-Author Impagliazzo

Russell Impagliazzo, who co-proposed the Exponential Time Hypothesis in 1998, called the AI-generated disproof "very shocking news," The New York Times reports, while adding that "most researchers expected stricter versions of the hypothesis to fall first."

The claim lands in two papers OpenAI and Anthropic announced on October 26: OpenAI's 67-page "The Exponential Time Hypothesis is False" and a 49-page companion from Anthropic. Both present algorithms for 3-SAT with running time of 2^o(n), and both say the proofs were written with heavy AI involvement and checked in Lean, a program that verifies mathematical proofs line by line. OpenAI says its AI found a "natural language disproof" on Oct. 16 and that the result was formalized the next day.

How much that changes anything in practice is a separate question. Anthropic said its result does not directly address whether P equals NP, and OpenAI said its speedup does not extend to NP problems in general. Outside estimates cited by the Times put OpenAI's checked bound as improving on brute force only beyond roughly 10 to the power of 2,389 variables; Anthropic wrote that, on 3-SAT formulas with five clauses per variable, its method would not beat brute force until problems exceeded 10^10,000 variables, far beyond anything that could ever be stored.

MIT's Ryan Williams, part of the review group with Impagliazzo and Ramamohan Paturi of UC San Diego, told TechCrunch there are "two or three alien-looking parts, and it's exactly these parts that I saw that made me think, wow, this is something that the whole community needs to work on together." The co-proposers were more guarded in a joint statement: "Our involvement should not be taken as certification of the claim."

Williams said the review group signed no non-disclosure agreements and will not be paid, and asked OpenAI to release all raw data on the ETH result and to fund a conference for the research community. OpenAI agreed to both.