ResearchCisent
OpenAI says its AI refuted a 1999 conjecture. What matters is how it gets checked
OpenAI says one of its models refuted the Exponential Time Hypothesis. It is under review, and what gives it weight is not the AI's confidence but the fact that it can be checked.

On October 26, OpenAI announced1 that an unnamed internal model wrote a manuscript titled “The Exponential Time Hypothesis is False”.2 If it survives review, a 1999 conjecture that many results in complexity theory rest on will fall. It is not confirmed yet. It will be examined by Russell Impagliazzo and Ramamohan Paturi, who proposed the conjecture, together with Ryan Williams of MIT.2
What the conjecture says
Its ground is 3-SAT, one of the most studied problems in computer science. You have a formula made of many small conditions, each on three variables that can only be true or false, and the question is whether there is a way to set the variables so that all of them hold. With n variables there are 2ⁿ possible combinations.
The Exponential Time Hypothesis, put forward by Impagliazzo and Paturi in 1999,3 says there is no fundamental shortcut: you can be smarter than trying them all, but the time needed will keep growing exponentially with the number of variables. Many results in complexity build on it: they say something cannot be done faster, if the conjecture is true.
What OpenAI claims
The manuscript presents a deterministic algorithm that counts exactly how many solutions formulas of this kind have, with conditions on three variables or any other fixed number, in a time that grows more slowly than any exponential and with memory that grows polynomially. The three-variable case, 3-SAT, is the one that refutes the conjecture.2
It does not settle P versus NP: the algorithm is faster than any exponential, but still slower than a polynomial one. That problem remains open.
Why it can be checked
A model can write a false proof with the same confidence as a true one. So what matters is not that an AI says it, but what surrounds the claim:
- A statement written separately. The theorem is written in Lean, a language in which a computer checks mathematical proofs, in a file separate from the proof.4
- A checker. A comparator verifies that the proof proves exactly that statement, and only lets it use three standard axioms: no shortcuts.5 The proof spans 3,977 Lean files.6
- The materials, in the open. OpenAI released them right away, at the request of the group that will examine the proof, so that others can review them too.2
- An independent review. Impagliazzo, Paturi and Williams will examine the proof and explain it.2 Examining it is not endorsing it: that work is just starting.
At Cisent we reviewed the formal statement, and it says what they announce. We did not run the full proof: OpenAI publishes it as the formal proof of that statement.7
Confidence is not proof
The same repository shows why all of that is needed. It holds 721 manuscripts from the same model, and about 42% of the main results have a formal proof. OpenAI warns that some of those without one could have issues.8 On October 7 it withdrew three manuscripts over a sign error and revised fourteen others.2
The one on the conjecture is among those that come with a formal proof.2
What does not change
- Encryption. Everyday cryptography does not rest on this conjecture, but on other assumptions.
- P versus NP. Still open.
The rule that matters
What makes an AI’s claim credible is not how confidently it is made, but whether it can be checked: a statement written separately, a checker, the materials in the open and a review that does not depend on whoever makes the claim. It is the rule we use to publish our own figures, each with the source behind it. And it is the idea behind our research on saying “I don’t know”: a model that knows when it does not know is worth more than one that always sounds sure. Our publications are in Research.
What we don’t know yet
- Whether the proof survives the examination by Impagliazzo, Paturi and Williams.
- Whether it passes the checker in other hands: we did not run it.
- From what formula size the algorithm beats exhaustive search: OpenAI did not publish its constants.
- How many of the other manuscripts will survive review: most still have no formal proof.8
Sources
OpenAI, announcement of October 26, 2026. https://openai.com/index/building-scientific-understanding-with-academic-communities/↩︎
OpenAI, openai/math repository, “History”, entries of October 7 and October 26, 2026 (version of October 26, commit 7ef5c0c). https://github.com/openai/math/blob/7ef5c0cc5ca4b0e072b7a050fca09ab24bc6fa3a/history.md↩︎
Russell Impagliazzo and Ramamohan Paturi, “Complexity of k-SAT”, Proceedings of the 14th Annual IEEE Conference on Computational Complexity, 1999, pp. 237-240 https://doi.org/10.1109/CCC.1999.766282. Journal version: “On the Complexity of k-SAT”, Journal of Computer and System Sciences 62(2), 2001, pp. 367-375 https://doi.org/10.1006/jcss.2000.1727.↩︎
OpenAI, the formal statement in Lean, “SubexponentialSAT.lean”. https://github.com/openai/math/blob/7ef5c0cc5ca4b0e072b7a050fca09ab24bc6fa3a/lean/ComparatorChallenges/SubexponentialSAT.lean↩︎
OpenAI, the comparator configuration, “SubexponentialSAT.json”: it only permits the axioms propext, Quot.sound and Classical.choice. https://github.com/openai/math/blob/7ef5c0cc5ca4b0e072b7a050fca09ab24bc6fa3a/lean/ComparatorChallenges/SubexponentialSAT.json↩︎
OpenAI, the proof’s folder, “lean/OAI/Algorithms/SubexponentialSAT”: 3,977 Lean files, counted by Cisent with the GitHub API at the cited version. https://github.com/openai/math/tree/7ef5c0cc5ca4b0e072b7a050fca09ab24bc6fa3a/lean/OAI/Algorithms/SubexponentialSAT↩︎
OpenAI, the formalization catalogue, “formalization.yaml”, which links the manuscript to its Lean proof. https://github.com/openai/math/blob/7ef5c0cc5ca4b0e072b7a050fca09ab24bc6fa3a/lean/formalization.yaml↩︎
OpenAI, openai/math repository, README (version of October 26). https://github.com/openai/math/blob/7ef5c0cc5ca4b0e072b7a050fca09ab24bc6fa3a/README.md↩︎