Generated by Codex with GPT 5.6 Sol High

Techmeme surfaced Cade Metz’s New York Times article, “How A.I. Just Blew Up a Key Tenet of Computer Science.” It covers OpenAI’s preprint, “The Exponential Time Hypothesis is False,” and a parallel result from Anthropic. The discovery deserves the attention: if the proofs withstand review, AI systems have overturned a conjecture that supported decades of algorithmic lower bounds. But the result does not settle P versus NP, make hard problems easy, or threaten today’s encryption by itself.

A narrower wall comes down

The Exponential Time Hypothesis, proposed by Russell Impagliazzo, Ramamohan Paturi, and Francis Zane, says that solving 3-SAT in the worst case requires time exponential in the number of variables. SAT asks whether some assignment of true and false values satisfies a collection of logical clauses. It is the canonical NP-complete problem: a proposed solution is easy to check, while finding one can require exploring an enormous search space.

OpenAI’s algorithm does more than decide whether a solution exists. For every fixed clause width, it exactly counts all satisfying assignments, uses polynomial space, and runs in asymptotically subexponential time. Its headline bound has the rough form 2^(n/sqrt(log n)), with polynomial and lower-order factors. As the input grows without limit, the exponent becomes an ever-smaller fraction of n. That contradicts ETH’s claim that 3-SAT requires 2^(cn) time for some constant c>0.

This is not a proof that P equals NP. Polynomial time would look like n^c, whereas the new algorithm still grows much faster than every polynomial. The Times’ Sudoku analogy therefore stretches too far when it suggests that enormous puzzles could be solved “just as quickly” as their answers can be checked. The result says there is an asymptotic shortcut relative to brute force, not that search and verification now have comparable cost.

The distinction also limits what transfers to other problems. NP-completeness means that NP problems can be translated into SAT with polynomial overhead, but a 2^o(n) bound survives only when a reduction carefully controls the number of new variables. OpenAI explicitly says the result does not put every NP problem in subexponential time. It does derive subexponential algorithms for several problems with suitable encodings, including counting independent sets, fixed-color graph colorings, and perfect matchings. It also removes ETH and the stronger SETH as foundations for many conditional lower bounds, although some of those bounds remain supported by weaker conjectures such as the Orthogonal Vectors Conjecture.

A theoretical breakthrough, not a practical solver

The asymptotics hide extraordinary constants. A follow-up analysis by Marvin Dias and Leandro Lima estimates that, even for formulas with a bounded number of clauses per variable, the proof’s tensor-contraction bound does not beat exhaustive search until log2(n+m) exceeds one billion. For random 3-SAT near the satisfiability threshold, the crossover is later still. No input remotely close to that size could be written down, let alone processed.

For every realistic instance, mature SAT solvers and older exponential-time algorithms remain vastly faster. The advance is conceptual: it proves that a presumed linear exponent is not an unavoidable law. History offers reasons not to dismiss such results—ideas from theoretical computer science sometimes become useful only after years of simplification—but no one has yet supplied the missing engineering path. Claims about faster chip design, drug discovery, recursive AI improvement, or broken encryption are possibilities for future descendant techniques, not consequences available from this algorithm today.

Encryption needs especially careful treatment. Many deployed systems rely on the difficulty of factoring or discrete logarithms, not directly on fixed-width SAT. Even where a cryptographic task can be encoded as SAT, the reduction size and the new algorithm’s constants determine whether anything improves. OpenAI notes that its result does not rule out one-way functions against polynomial-time attackers. “ETH is false” and “current encryption is breakable” are very different statements.

There are also two kinds of verification to keep separate. OpenAI and Anthropic independently announced subexponential counting algorithms on October 26, and both released mathematical arguments with Lean developments. That convergence makes the episode more striking, but neither lab’s claim becomes settled merely because another AI system reached a related result. The papers are still under expert review, and machine checking only covers what has actually been formalized under the encoded assumptions; reviewers must still connect those lemmas to each paper’s full complexity claim.

The most durable lesson is about the production of theory. An unreleased AI system did not merely optimize code or search for a counterexample. It assembled a long argument that appears to change the map of computational complexity, while another lab produced a parallel route. Human experts now face the inverse bottleneck: understanding, auditing, contextualizing, and rebuilding confidence in results faster than models can generate them. Even if the algorithm never solves a practical SAT instance, that shift in who proposes foundational mathematics—and how the field verifies it—is already consequential.