Russell Impagliazzo reportedly called it “shocking news.” The theoretical computer scientist was reacting to the OpenAI Exponential Time Hypothesis claim: an internal AI system had apparently found a mathematical result contradicting a foundational assumption that Impagliazzo helped formulate nearly three decades ago. If the result survives expert scrutiny, it could change how researchers think about difficult computational problems. It does not, however, mean that artificial intelligence can suddenly crack RSA, compromise Bitcoin, or defeat the encryption protecting the internet.
OpenAI says its system discovered a deterministic, subexponential-time algorithm for exactly counting the satisfying assignments of fixed-width Boolean formulas. The company has released a preprint and a formalization in the Lean theorem prover while working with Impagliazzo, Ramamohan Paturi, and Ryan Williams to examine the argument. As of November 2026, this remains an extraordinary research claim rather than a result that has completed independent peer review.
The Exponential Time Hypothesis explained
The Exponential Time Hypothesis, or ETH, is an influential conjecture in computational complexity theory. Proposed by Impagliazzo and Paturi, it concerns how quickly computers can solve certain versions of the Boolean satisfiability problem.
A Boolean formula combines variables that can be either true or false. In the well-known 3-SAT problem, the formula is divided into clauses containing up to three conditions. A computer must determine whether there is any assignment of true and false values that makes every clause true.
Trying every possibility for n variables requires examining as many as 2n assignments. That growth is exponential: adding variables can make the search dramatically harder. Clever algorithms avoid much of this brute-force work, but ETH proposes that 3-SAT still cannot be solved in subexponential time, commonly expressed as 2o(n).
This is not a proven law. It is a working hypothesis that has supported hundreds of conditional lower-bound results. Researchers often use ETH to argue that a faster algorithm for one problem would imply an unexpectedly fast algorithm for SAT. If ETH is false, those papers do not automatically become useless, but conclusions stated conditionally on ETH would need to be reassessed.
What OpenAI says its AI discovered
The OpenAI AI mathematical breakthrough centers on exact counting rather than simply finding one satisfying assignment. Given a fixed-width Boolean formula, the claimed algorithm counts every assignment that satisfies it. This is a form of the #SAT, or model-counting, problem.
Exact counting is important because it also answers the ordinary satisfiability question. If the count is greater than zero, the formula is satisfiable. If it is zero, no solution exists. Consequently, a sufficiently general subexponential algorithm for exact counting would also provide a subexponential method for deciding satisfiability and would contradict ETH.
OpenAI describes the method as deterministic, meaning it does not depend on randomness for its guarantee. It is also claimed to be subexponential in the number of variables for formulas of fixed clause width. The precise quantifiers, input model, width restrictions, uniformity conditions, and hidden constants matter enormously. Those details determine whether the theorem truly reaches the standard formulation of ETH rather than a narrower variant.
This is why the preprint—not a summary headline—is the decisive document. Independent theorists must check the algorithm, complexity analysis, boundary cases, and connection between the formal theorem and the conventional hypothesis.
Why the Lean formalization matters—and what it cannot prove
OpenAI has accompanied the mathematical argument with a formalization in Lean, a proof assistant that can verify whether a proof follows from explicitly defined assumptions and inference rules. Lean reduces the risk of overlooked algebraic steps, inconsistent definitions, or informal leaps in reasoning.
A machine-checked proof is strong evidence that the encoded theorem follows from the encoded premises. It is not identical to broad scientific acceptance. Experts still need to determine whether the formal statement accurately represents the intended algorithm, whether its cost model matches standard computational complexity, and whether imported assumptions or abstractions hide a material gap.
Software surrounding a proof can also contain errors, although Lean’s small trusted kernel is designed to minimize that risk. Formal verification therefore strengthens the claim without eliminating the need for independent mathematical review, reproduction, and peer-reviewed publication.
Human experts remain central to the review
According to OpenAI’s announcement and New York Times reporting, the company is collaborating with Impagliazzo, Paturi, and Williams to evaluate the result. That involvement is significant: Impagliazzo and Paturi co-developed ETH, while Williams is known for major work in algorithms and complexity theory.
OpenAI has also committed to releasing supporting research materials and funding an academic conference where specialists can investigate the work. Transparency will be crucial. Researchers need access to the formal definitions, source code, proof files, algorithmic construction, and complexity analysis—not merely outputs attributed to an internal model.
Impagliazzo’s reported “shocking news” reaction captures the potential importance of the development, but it should not be read as final validation. Surprise from a leading expert is a newsworthy signal, not a substitute for consensus.
Asymptotic progress is not the same as a practical speedup
“Subexponential” sounds fast, but it does not necessarily mean useful. An algorithm running in 2√n time is subexponential yet can still be impossibly expensive on large inputs. Huge constant factors, memory requirements, preprocessing costs, or thresholds at which the asymptotic advantage begins may make a theoretically superior method slower in practice.
The claimed algorithm could therefore disprove ETH while offering no meaningful performance improvement for realistically sized formulas. Experimental implementations and concrete benchmarks would be needed before anyone could describe it as a practical solver.
This distinction is common in AI algorithm discovery. A new asymptotic bound can transform theory even when engineers cannot immediately deploy it. Later researchers may simplify the method, improve its constants, combine it with existing solvers, or apply its central insight elsewhere.
Possible effects on optimization and AI chip design
SAT solving and related optimization methods appear throughout engineering. Electronic design automation uses them in circuit verification, logic synthesis, test generation, scheduling, and some placement and routing workflows. Model counting also helps analyze reliability, configurations, and the number of states satisfying specified constraints.
If the underlying ideas lead to practical algorithms, AI chip design optimization could benefit. Engineers might verify larger designs, explore more candidate layouts, or prove properties of complex processors more efficiently. The discovery could also inspire algorithms for planning, operations research, software verification, and scientific modeling.
Those possibilities remain long-term research directions. The current claim is a mathematical complexity result, not a production-ready chip-design tool. Translating it into useful software may require years of additional work—or may never yield a practical advantage.
Could the result eventually break encryption?
The short answer is that it does not break today’s encryption. RSA security is associated with the difficulty of factoring large integers. Elliptic-curve cryptography relies on discrete-logarithm problems in carefully selected groups. Bitcoin uses elliptic-curve signatures and cryptographic hash functions. None of those systems is directly defeated by a subexponential algorithm for fixed-width Boolean model counting.
There is nevertheless a legitimate reason to study AI and cryptography together. Cryptographic attacks can sometimes be encoded as SAT or constraint problems. Better general-purpose algorithms may improve automated cryptanalysis, help researchers search for weaknesses, or alter assumptions used in proofs and security estimates.
But reductions have overhead. Converting a cryptographic problem into a Boolean formula can introduce many variables and clauses, while asymptotic improvements may arrive with enormous constants. A theoretical subexponential SAT algorithm is not automatically a competitive factoring, discrete-logarithm, key-search, or hash-collision algorithm.
The result also does not reveal private keys, reverse secure hashes, or undermine encrypted web sessions. Any future security impact would require additional breakthroughs: practical implementations, efficient encodings, better concrete bounds, and evidence that the method outperforms specialized cryptanalytic techniques.
Why this does not resolve P versus NP
ETH and P versus NP are related but distinct. P versus NP asks whether problems whose solutions can be checked efficiently can also be solved in polynomial time. ETH makes a stronger claim about the absence of subexponential algorithms for 3-SAT.
ETH could be false while P still differs from NP. For example, SAT might admit a 2√n-time algorithm: that would be subexponential but not polynomial. Disproving ETH would therefore narrow the landscape of possible complexity behavior without proving that every difficult problem has an efficient solution.
Nor would one algorithm make all NP-hard problems easy in practice. Reductions preserve certain theoretical relationships, but input expansion, constants, approximation requirements, and problem structure determine real performance.
AI as a mathematical research collaborator
Beyond ETH, the episode may become a landmark in AI scientific discoveries. AI systems have already assisted with theorem proving, code generation, symbolic reasoning, and searches through large combinatorial spaces. Producing a genuinely new algorithmic theorem would move AI from supporting calculations toward proposing research that changes a field’s assumptions.
That transition creates difficult questions. How should credit be divided among model developers, prompt designers, formalization engineers, and mathematicians who verify and interpret the result? What information about training data, search procedures, failed attempts, and human intervention should be disclosed? Can outside researchers reproduce a discovery made by a proprietary internal system?
Human expertise remains indispensable. Specialists must identify why a statement matters, test whether definitions match established literature, challenge hidden assumptions, and connect abstract results to other fields. AI may expand the search space of ideas, but scientific acceptance still depends on transparent evidence and informed criticism.
What researchers will examine next
- Whether independent experts can reproduce every step of the algorithm and complexity bound.
- Whether the Lean statement exactly captures the version of ETH that OpenAI says it contradicts.
- How the method behaves on finite, realistic problem sizes.
- Whether its core techniques generalize to other counting, optimization, or cryptographic problems.
- Whether the preprint survives peer review without substantial changes to its main conclusion.
Until that process advances, the most accurate description is both exciting and cautious: OpenAI has presented a formalized claim that could overturn a 27-year-old assumption, but the broader conclusion has not yet earned independent scientific consensus.
Frequently asked questions
Did OpenAI’s AI prove that the Exponential Time Hypothesis is false?
OpenAI claims that its AI discovered a deterministic subexponential-time exact-counting algorithm that would contradict ETH. It has provided a preprint and Lean formalization, but the broader claim still requires independent expert verification and peer review.
Can this algorithm crack RSA or elliptic-curve encryption?
No. The reported result addresses fixed-width Boolean formulas, not a direct algorithm for factoring integers or solving elliptic-curve discrete logarithms. Future algorithmic insights could influence cryptanalysis, but no current evidence shows that RSA, elliptic-curve cryptography, or ordinary internet encryption has been broken.
Does disproving ETH prove that P equals NP?
No. A subexponential algorithm may still require superpolynomial time. ETH can be false even if P and NP remain different, so the result would not settle computer science’s most famous open problem.
Why is the result important if the algorithm is not practical?
Complexity theory maps the fundamental limits of computation. Removing a widely used assumption could change conditional lower bounds, inspire new AI algorithm discovery, and reveal techniques that later become more efficient. The theoretical impact can be substantial even without an immediate commercial application.
