OpenAI says a logic shortcut leaves P versus NP open

OpenAI says an internal system wrote a disproof of the exponential time hypothesis on October 16, 2026, and a Lean formalization of that argument on October 17.

The company has put both files on a public repository and asked complexity theorists outside the company to examine them.

The hypothesis means a claim about one family of logic puzzles. A formula in 3-SAT asks whether some assignment of true and false makes every clause true. Checking a finished assignment is quick. Finding one, in the worst case, is what the hypothesis treats as exponential in the number of variables. Researchers have used that premise in hundreds of papers. Those papers then say that some other problem is hard if the hypothesis is true. The fields named on OpenAI's October 26 page are graph theory, computational biology, databases, and computational geometry. If the premise is false, those conditional limits lose the reason they were treated as tight. The reductions written in those papers remain.

How the reported argument works, on OpenAI's own account, is a count. The system is said to count satisfying assignments with a deterministic procedure. A count of zero means the formula has no solution, so the same procedure also decides the yes-or-no question. OpenAI says its Lean check accepted the formalization on October 17. It calls the natural-language writeup raw research data. It does not present that writeup as the outside group's explanation.

Russell Impagliazzo and Ramamohan Paturi of the University of California, San Diego, proposed the hypothesis with Francis Zane. They are leading the outside group with Ryan Williams of the Massachusetts Institute of Technology. OpenAI says the group asked for the raw material to be public and for the company to fund a conference. Participation is voluntary and unpaid. OpenAI says it is not taking academic credit for the model output, and that the group's conclusions are their own.

P versus NP asks whether every problem whose answer can be checked quickly can also be solved quickly. The exponential time hypothesis is related to that question. A bound that is faster than a full exponential can still be slower than every polynomial, so a refutation of the hypothesis does not by itself answer P versus NP. Leslie Goldberg of the University of Oxford told New Scientist that the result, if confirmed, would be a large break in complexity theory and would not count as progress on P versus NP. Williams told TechCrunch that computer scientists should put a little more weight on the possibility that P equals NP, that the amount of extra weight can differ by person, and that he does not think the reported algorithm is the best possible one. He also said, as TechCrunch reported it, that OpenAI was reasonably confident no cryptosystem had been broken. RSA and elliptic-curve security, on that account, do not rest on the hypothesis.

The shepherd group has not yet published its own writeup. Until that account exists, the public record is the company's files plus the comments those researchers have already given to other outlets.