AI Models Claim to Refute Computational Complexity Hypothesis? Experts Weigh In

An Unexpected Claim

According to TechCrunch, several frontier AI labs have claimed that their models achieved a breakthrough in computational complexity theory: they "refuted" the famous Exponential Time Hypothesis (ETH). This claim quickly sparked heated discussion in the tech community, as ETH is a widely accepted foundational assumption in theoretical computer science. To clarify the truth, TechCrunch interviewed a computer scientist at MIT who specializes in explaining OpenAI's latest findings to the public.

What Is the Exponential Time Hypothesis?

ETH was proposed by computer scientists Russell Impagliazzo and Ramamohan Paturi in the 1990s. It asserts that for NP-complete problems such as 3-SAT, there is no algorithm that runs in subexponential time (i.e., O(2^{o(n)})). In other words, as problem size grows, solving time explodes exponentially and cannot be substantially compressed through algorithmic optimization. ETH is not a proven theorem but a strong hypothesis indirectly supported by a large body of algorithm research. If it were refuted, many lower-bound results in complexity theory would collapse, and it could even affect the foundations of cryptography.

NP-Complete Problems and 3-SAT

NP-complete problems are those that belong to the NP class (solutions can be verified in polynomial time) and to which all NP problems can be reduced in polynomial time. 3-SAT is the first problem proven to be NP-complete (the Cook-Levin theorem). Its form is: given a Boolean formula composed of multiple clauses, each containing exactly three literals (variables or their negations), determine whether there exists an assignment of variables that makes the entire formula true. The NP-completeness of 3-SAT makes it a standard vehicle for studying computational complexity lower bounds. ETH uses 3-SAT as its benchmark: it asserts that no algorithm for 3-SAT can run in O(2^{o(n)}) time, where n is the number of variables. This hypothesis matters because lower bounds for many other problems can be derived through fine-grained reductions from 3-SAT.

The AI Labs' Claim and the MIT Expert's Interpretation

According to TechCrunch, frontier AI labs claim that their models found some kind of counterexample or construction sufficient to negate ETH. But the MIT computer scientist urged the public in the interview to remain cautious. He explained that patterns discovered by AI models in mathematics are not equivalent to rigorous mathematical proof. Models may produce seemingly plausible "proofs" that contain hidden logical gaps or misunderstandings of definitions. He stressed that any work claiming to refute ETH must undergo formal verification and peer review, and the information currently public is far from meeting that standard.

Why Do AI's Mathematical Discoveries Require Rigorous Verification?

In recent years, AI-assisted discoveries in mathematics have become common, for example helping generate conjectures, find counterexamples, or simplify proofs. But these results usually require rigorous formal verification by human mathematicians. For a foundational hypothesis like ETH, refuting it means either providing a subexponential algorithm that holds for all instances or proving that none exists. AI models may have merely found fast solutions on specific small-scale instances, but that cannot refute ETH—ETH concerns asymptotic behavior. The MIT expert pointed out that the labs' claims may conflate "performing well at finite scale" with "theoretically breaking a lower bound."

Asymptotic Behavior and Formal Verification

Asymptotic behavior describes how an algorithm's running time grows as input size n tends to infinity, often expressed using notations such as big-O and small-o. ETH concerns whether, as n tends to infinity, there exists an algorithm with time complexity O(2^{o(n)})—that is, whether the exponent grows more slowly than any linear function. Fast solutions observed on finite-scale instances (for example, performing well when n=100) cannot be generalized into an asymptotic conclusion, because constant factors and lower-order terms may dominate when n is small, while asymptotic analysis ignores these factors.

Formal verification refers to using computer programs (such as the proof assistants Coq, Lean, and Isabelle) to translate mathematical proofs into a machine-checkable form, verifying step by step whether each logical deduction conforms to axioms and inference rules. For results claiming to refute foundational hypotheses like ETH, formal verification can rule out hidden logical gaps, misuse of definitions, or circular reasoning. At present, most AI-generated mathematical proofs have not undergone formal verification, so their reliability requires rigorous scrutiny by human experts.

Implications for AI for Science

Although this claim may be exaggerated, it reflects AI's growing involvement in theoretical science. AI models can explore proof spaces that are difficult for humans to exhaustively search and propose counterintuitive constructions, which is valuable in itself. However, the scientific community needs to establish stricter verification processes for AI-assisted proofs to avoid treating model outputs that look like "suspected breakthroughs" as established facts. TechCrunch's report reminds us that, amid the excitement, maintaining theoretical rigor remains the cornerstone of scientific progress.

One-line Summary

AI labs claim to have refuted ETH; MIT experts stress the need for rigorous formal verification.

Paragraph Summary

Several frontier AI labs claim their models have refuted the Exponential Time Hypothesis (ETH) in computational complexity theory, sparking heated discussion in the tech community. Proposed by Impagliazzo and Paturi in the 1990s, ETH asserts that NP-complete problems such as 3-SAT have no subexponential-time algorithms; it is a widely accepted but unproven strong hypothesis. In an interview, an MIT computer scientist cautioned that patterns discovered by AI are not equivalent to rigorous mathematical proof, and models may produce seemingly plausible "proofs" with logical gaps. He stressed that refuting ETH requires either a subexponential algorithm valid for all instances or a proof that none exists, and fast solutions on finite-scale instances cannot negate ETH's asymptotic conclusions. The episode reflects AI's growing role in theoretical science, but the scientific community needs stricter verification processes for AI-assisted proofs.