OpenAI’s AI Didn’t Settle The Exponential Time Hypothesis—Here’s The Nuance

🔍 Read the full analysis: OpenAI’s AI Didn’t Settle The Exponential Time Hypothesis—Here’s The Nuance on ThorstenMeyerAI.com

OpenAI said on October 26 that an unreleased internal AI model had produced a proof challenging the Exponential Time Hypothesis (ETH), a longstanding assumption about the difficulty of solving certain logic problems. The company published a preprint and Lean formalization, but the result has not yet received independent expert sign-off, and the formalized statement uses a weaker runtime bound than the paper’s sharpest claim.

The preprint describes a deterministic algorithm for exactly counting solutions to k-SAT, where the clause size k is fixed, that runs in subexponential time and uses polynomial memory. For 3-SAT, the claim contradicts ETH, which holds that no algorithm can solve the problem in subexponential time. The paper also says the result refutes the stronger Strong Exponential Time Hypothesis and three related hypotheses.

OpenAI says its system found the disproof on October 16, and that the Lean formalization followed on October 17. The company released the preprint and code at the request of an outside group that will examine the computer-science result. The source account reports that the Lean material comprises 3,977 files and about 710,000 lines; those are its own counts, rather than figures independently confirmed here.

There is an important qualification: according to the source account’s inspection of the Lean scope notes, Lean checks a slightly weaker runtime bound than the paper’s sharpest version. The proof has been machine-checked, but that does not amount to independent review of the mathematical argument or confirm every claim in the preprint. The outside review is still in progress.

What an ETH Refutation Would Change

If the result survives scrutiny, it would overturn a widely used assumption about how quickly certain problems can be solved. Researchers use ETH and related conjectures to establish lower bounds and argue that algorithms for many problems cannot run substantially faster than current methods. A valid counterexample could require those arguments to be revisited.

The result is not a practical speed breakthrough. The reported runtime is roughly 2 to the power of n divided by the square root of log n: subexponential, but still far slower than polynomial time. OpenAI says practical improvements would require significant further research. The claim also does not solve P versus NP, the separate open question of whether every problem whose solutions can be checked quickly can also be solved quickly.

For readers beyond theoretical computer science, the immediate significance is also methodological. The episode tests a proposed route for evaluating AI-produced mathematics: publish the work, formalize a proof so a proof assistant can check it, and ask independent experts to examine the result. Formal checking can catch errors within the statement encoded in Lean; it does not, by itself, establish that the formal statement matches every claim in a paper or that the discovery has useful applications.

How the ETH Claim Fits the Field

In k-SAT, each rule contains at most k variables or their negations, and the task is to determine whether truth values can satisfy all the rules. With n variables, checking every possible assignment takes 2ⁿ combinations. Researchers have found faster exact algorithms, but those methods still take exponential time. ETH, proposed by Russell Impagliazzo, Ramamohan Paturi and Francis Zane in 2001, conjectures that 3-SAT cannot be solved in subexponential time.

The source account cites algorithms with progressively smaller exponential bases, including Schöning’s 1999 method and later PPSZ refinements. ETH is stronger than the claim that P differs from NP: disproving ETH would remove that particular stronger hardness assumption, but would not show that 3-SAT has a polynomial-time algorithm or settle the P-versus-NP question.

OpenAI presented the ETH work alongside claims in mathematics and physics. Its announcement described a proof concerning Sogge’s local smoothing conjecture and related conjectures, and a physics result involving quantum chromodynamics and the Standard Model. According to the source account, the physics materials are being held back at the request of an outside group, while the mathematics materials were released. These are separate claims and do not independently validate the computer-science result.

What the Formal Proof Covers

The main open issue is whether independent experts agree that the paper’s argument is correct and that its formalized version supports the stated conclusions. The source account says a group led by Russell Impagliazzo, Ramamohan Paturi and Ryan Williams will examine the proof; Impagliazzo and Paturi were among ETH’s original authors. No final assessment from that group is provided in the supplied material.

The difference between the preprint’s sharpest runtime bound and the weaker bound checked in Lean also needs to be resolved or clearly characterized. The available account does not establish whether the gap affects the headline ETH contradiction or which of the additional claims about SETH and related hypotheses are covered by the formalization. Nor does it report a completed peer review or practical applications.

OpenAI’s announcement describes the model and the research process, but the supplied material does not provide a full independent account of the model’s capabilities or a separate replication of its work. The company’s account of how the result was produced should therefore be distinguished from the proof’s mathematical status.

Independent Review and Formal Scope

The next milestone is the outside group’s examination of the computer-science preprint and its Lean materials. Readers will need a public account of whether reviewers accept the proof, whether the Lean statement matches the paper’s claims, and how the difference in runtime bounds affects the result.

Further updates may also clarify the status of the claimed consequences for SETH and the related hypotheses, and whether other researchers can independently reproduce or extend the work. Until those checks are reported, the defensible description is that OpenAI has announced a potential ETH refutation, with a machine-checked formalization of a related, weaker statement and expert review still pending.

Key Questions

What did OpenAI’s AI claim to prove?

OpenAI says an internal model produced a proof of a subexponential-time algorithm for exactly counting k-SAT solutions for fixed k. Applied to 3-SAT, the claim contradicts ETH if the proof and stated runtime are correct.

Has the proof been verified?

A version has been checked in Lean, a proof assistant, but the supplied account says the formalized bound is slightly weaker than the preprint’s sharpest bound. Independent expert review has not concluded, so the result should not be treated as fully settled.

Does this solve P versus NP?

No. The proposed algorithm remains slower than polynomial time. A refutation of ETH would challenge a stronger hypothesis about exponential running times, not settle the P-versus-NP problem.

Could this make SAT solving faster in practice?

That is not established. The claimed subexponential runtime is still extremely large, and OpenAI said practical improvements would require significant further research.

Source: ThorstenMeyerAI.com