OpenAI challenges a key hypothesis in theoretical computer science
OpenAI claims to have disproved the exponential time hypothesis, a cornerstone of theoretical computer science. The proof, formalized in Lean and published on GitHub, still needs independent review.
OpenAI claims to have refuted the exponential time hypothesis, a central idea that assumes some cases of 3-SAT require exponential computation time. If this proof is confirmed, it would challenge a major limit in theoretical computer science, without resolving the P versus NP problem. The result, formalized in Lean and published on GitHub, remains to be examined by independent researchers, including those who originally proposed the hypothesis.
When a hypothesis stands for decades, the cost becomes heavy
The announcement is significant mainly for what it affects: a theoretical safeguard that structures part of research in algorithmic complexity. In this case, OpenAI says it has found a proof contradicting the idea that the hardest instances of 3-SAT necessarily require exponential time. The decisive point is not only the thesis itself but the way it must be verified, as the scientific community does not validate such results based solely on a press release. A proof formalized in Lean facilitates examination but does not shorten it.
Validation still awaited, and this is where everything is at stake
The use of Lean, a formal proof assistant, reduces the risk of logical errors in the demonstration. However, publication on GitHub does not equate to academic validation, especially when the result contradicts such an established hypothesis. OpenAI specifies that the proof must still be independently scrutinized, notably by the two researchers associated with the original hypothesis. In short, the hardest part often begins after the announcement. Theoretical computer science loves proofs, but it loves proofs reviewed by others even more.
Why this announcement goes beyond the laboratory
If confirmed, this breakthrough could influence how researchers approach certain combinatorial problems and the computational bounds once thought established. However, it would not end the P versus NP debate, which remains one of the major open problems in the field. The real impact will therefore depend less on the spectacular nature of the announcement than on its robustness under external review. For now, the topic mainly interests fundamental research, but the symbolic effects are already clear: when a supposedly solid hypothesis wavers, an entire part of the playing field changes perspective.
Key points
- OpenAI speaks of a refutation of the exponential time hypothesis.
- The proof is formalized in Lean and published on GitHub.
- Two researchers linked to the hypothesis still need to examine it.
- P versus NP is not resolved by this announcement.
By the numbers
- 3-SAT — problem cited by OpenAI as a difficult case.
- 1 hypothesis — the exponential time hypothesis, at the heart of the announcement.
- 2 researchers — associated with the hypothesis and expected to review it.