OpenAI Claims an Internal Model Broke the 3-SAT Boundary

Key Takeaways

• OpenAI reported three theoretical discoveries across harmonic analysis, complexity theory, and quantum field theory.
• An internal OpenAI model claims to solve 3-SAT problems faster than the limit set by the Exponential Time Hypothesis.
• The model checked its own proof in Lean, a software system built for computer-verified mathematics.
• Original theorists Russell Impagliazzo and Ramamohan Paturi, joined by MIT's Ryan Williams, are leading the public review of the proof.
• Jordi Hays points out that when AI labs open-source pure math proofs, they are likely sitting on far more commercial breakthroughs behind closed doors.

When an AI Algorithm Challenges Complexity Theory

Computer scientists have spent decades treating the Exponential Time Hypothesis as a wall. Formulated by Russell Impagliazzo and Ramamohan Paturi, the hypothesis focuses on 3-SAT, a classic problem where you must decide if a logical formula can be satisfied. Impagliazzo and Paturi suggested that the difficulty of these problems is not due to a lack of human skill. As John Coogan explained, the hypothesis states that “this explosion is no longer a failure of human cleverness, but a law of nature, no algorithm, however brilliant, will ever solve threes without the time blowing up exponentially.”▶ 24:54

Now OpenAI claims an internal system found a way through that wall. Coogan noted that “an internal model at OpenAI claims to have broken it. It says it found an algorithm that solves these puzzles meaningfully faster than the hypothesis allows and it has checked the proof in a computer verification system called lean.”▶ 25:27

Instead of trusting the model blindly, OpenAI turned to the math community. The review process carries real drama: Impagliazzo and Paturi themselves, joined by MIT computer scientist Ryan Williams, are examining the machine's work to see if it disproved their idea. Coogan highlighted this dynamic: “The very people who propose the hypothesis along with MIT's Ryan Williams are now leading the public review of whether a machine has dis disproved their own idea.”▶ 25:43

The Real Discoveries Stay Private

Solving an abstract logic puzzle in Lean expands academic theory, but it produces zero direct revenue. That split is where builders should pay attention. AI labs share theoretical wins precisely because they carry little competitive danger.

Jordi Hays framed the announcement as an indicator of what remains hidden: “Anytime you see a breakthrough like this that is like against a sort of an open problem that's just generally expanding humanity's knowledge that isn't exactly immediately commercial, you have to assume there's many other highly commercial discoveries happening in the background.”▶ 27:02

When a model can verify complex symbolic logic in Lean, its reasoning engine can also tackle database optimization, logistics, code generation, and chip design. The pure math that labs publish for status signals the strength of private tools they run on commercial problems. The gap between what labs show the public and what they deploy internally is widening.

What to Do With This

Map the hardest computational bottlenecks in your current software architecture this week. Identify whether you run expensive heuristics on logic or scheduling problems because you assumed an exact answer was computationally impossible. Test an open-source formal theorem checker or automated solver on one constrained rule-set to see if modern verification tools catch edge cases your engineers missed.