OpenAI Says the Exponential Time Hypothesis Is False: What Changes in 2026

Hello HaWkers, on October 26, 2026, OpenAI published a preprint in its public openai/math repository with a title that sounds like a provocation: "The Exponential Time Hypothesis is False". The document is dated October 25, is signed only as "OpenAI", and comes with a formalization in Lean. Alongside it, the company announced two more results: one in mathematical analysis tied to the Kakeya conjecture, and another in theoretical physics, about the existence of quantum field theories in four dimensions.

The Exponential Time Hypothesis, known as ETH, is one of the assumptions that support a large part of modern algorithm theory. If it falls, dozens of results that say "this problem cannot be solved faster than X, assuming ETH" lose their foundation.

But what exactly was claimed? Does this break cryptography? Does it settle P versus NP? And why are so many serious people treating the announcement with caution? In this article you will understand ETH from scratch, see in code why SAT is so hard, compare the growth curves involved, and separate what has already been checked from what is still just a claim.

What Is the Exponential Time Hypothesis

To understand ETH, start with the SAT problem. You get a logical formula with boolean variables and need to answer: is there an assignment of true and false values that makes the whole formula true?

The most studied version is 3-SAT, where the formula is a conjunction of clauses and each clause has at most three literals. Something like:

(x1 OR NOT x2 OR x3) AND (NOT x1 OR x2) AND (x2 OR NOT x3 OR x4)

3-SAT is NP-complete. That means if someone found a polynomial algorithm for it, they would have proved P = NP. Almost nobody believes that, but "not polynomial" still leaves a lot of room. An algorithm that runs in 2^(n^0.5) steps is not polynomial, but it is absurdly faster than 2^n.

That is where Russell Impagliazzo and Ramamohan Paturi came in, in the late 1990s. They formulated the Exponential Time Hypothesis, which says, in simplified form:

There is a constant c > 0 such that no algorithm solves 3-SAT with n variables in time 2^(c·n) or less.

In other words, ETH bets that 3-SAT requires genuinely exponential time in the number of variables. It is not just "not polynomial": it is truly exponential, with no subexponential shortcut.

Why ETH matters so much

ETH became a working tool. Algorithm researchers use reductions to say things like "if you solve problem Y in time 2^o(n), you also solve 3-SAT in that time, contradicting ETH". That way, ETH serves as the basis for conditional lower bounds in graphs, optimization, parameterized algorithms, and much more.

There is also a stronger version, SETH (Strong Exponential Time Hypothesis), which states that for k-SAT with large k the exponent approaches 2^n. Many "fine-grained complexity" lower bounds depend on SETH. Since SETH implies ETH, if ETH is false, SETH falls too.

What OpenAI Claims to Have Proved

According to the announcement and the first analyses of the preprint, the central result is a deterministic algorithm that counts exactly how many assignments satisfy a k-CNF formula with fixed clause width, running in subexponential time and polynomial space.

Three details stand out:

It is counting, not just decision. Counting how many solutions exist (the #SAT problem) is usually harder than just answering whether one exists. A fast counting algorithm solves the decision problem for free.
It is deterministic. It does not depend on luck or randomness.
It uses polynomial space. It does not trade time for a mountain of memory.

Since 3-SAT is a special case, an algorithm like this would refute ETH. OpenAI itself wrote: "Surprisingly, our system has recently proved that the ETH is false".

What is the running time

Here the sources still disagree on the details. Comments in the Hacker News discussion and published analyses describe the bound as something on the order of 2^(n/√log n), with extra factors involving log log n in the exponent. For our reasoning, what matters is the general shape: the exponent grows like n divided by something that also grows. That is smaller than any 2^(c·n) for large enough n, which is exactly what ETH says is impossible.

At the same time, the algorithm is still superpolynomial. It does not prove P = NP. ETH is a stronger assumption than P ≠ NP, so knocking it down leaves the millennium question exactly where it was.

In Practice: Why SAT Explodes

Before looking at curves, it is worth feeling the problem with code. The naive way to count the solutions of a formula is to test all 2^n assignments:

// A CNF formula is a list of clauses.
// Each clause is a list of literals: 3 means x3, -3 means NOT x3.
const formula = [
  [1, -2, 3],
  [-1, 2],
  [2, -3, 4],
];

// Counts how many assignments satisfy the formula by testing all of them.
function countSolutions(clauses, n) {
  let total = 0;
  // Each number from 0 to 2^n - 1 represents a different assignment.
  for (let mask = 0; mask < 1 << n; mask++) {
    const value = (v) => ((mask >> (v - 1)) & 1) === 1;
    const satisfies = clauses.every((clause) =>
      clause.some((lit) => (lit > 0 ? value(lit) : !value(-lit)))
    );
    if (satisfies) total++;
  }
  return total;
}

console.log(countSolutions(formula, 4)); // number of solutions with 4 variables

With 4 variables, that is 16 tests. With 40, it is already over a trillion. With 100, the number of assignments has 31 digits. This is the wall every SAT algorithm tries to get around.

The algorithms that already existed

Nobody solves SAT by brute force. Real solvers use variations of DPLL and CDCL, which propagate logical consequences and prune entire branches of the search. A minimal version of DPLL looks like this:

// Simplifies the clauses assuming the literal `lit` is true.
function assign(clauses, lit) {
  return clauses
    .filter((c) => !c.includes(lit)) // satisfied clause disappears
    .map((c) => c.filter((l) => l !== -lit)); // false literal is removed
}

// DPLL: decides whether the formula has a solution.
function dpll(clauses) {
  if (clauses.length === 0) return true; // everything satisfied
  if (clauses.some((c) => c.length === 0)) return false; // conflict

  // Unit propagation: a clause with a single literal forces its value.
  const unit = clauses.find((c) => c.length === 1);
  if (unit) return dpll(assign(clauses, unit[0]));

  // Branching: pick a literal and try both values.
  const lit = clauses[0][0];
  return dpll(assign(clauses, lit)) || dpll(assign(clauses, -lit));
}

console.log(dpll([[1, -2, 3], [-1, 2], [2, -3, 4]])); // true

In practice, CDCL solvers handle industrial instances with millions of variables. But in the theoretical worst case, every known algorithm for 3-SAT was still exponential. The best classical bound came from the PPSZ family of algorithms (Paturi, Pudlák, Saks, and Zane), which runs in something close to 1.307^n. That is still 2^(c·n), with c around 0.386. Fast for an exponential algorithm, but exponential.

Comparing the Growth Curves

The best way to see the difference between "exponential" and "subexponential" is to put the numbers side by side. The code below compares the exponents (in base 2) of brute force, PPSZ, and a bound of the form n/√log n, ignoring the constants hidden in O notation:

// Base-2 exponent of each bound, so we can compare without overflowing Number.
const bounds = {
  bruteForce: (n) => n, // 2^n
  ppsz: (n) => n * Math.log2(1.307), // roughly 1.307^n
  subexponential: (n) => n / Math.sqrt(Math.log2(n)), // 2^(n / √log n)
};

for (const n of [16, 64, 256, 1024, 65536, 1e9]) {
  const line = Object.entries(bounds)
    .map(([name, f]) => `${name}: 2^${f(n).toFixed(1)}`)
    .join(" | ");
  console.log(`n=${n} -> ${line}`);
}

When you run it, you notice two things. First, for small n, PPSZ wins, because √log n grows far too slowly. Second, for large n, the ratio between the subexponential exponent and n goes to zero, while the PPSZ ratio stays stuck at 0.386. That asymptotic difference is what knocks down ETH.

What "galactic" means

In the Hacker News discussion, a SAT expert summed it up: the result has no immediate application, the algorithms are "galactic". That is an informal technical term for algorithms that are asymptotically better but only beat existing methods at input sizes that will never show up in the real world.

You can illustrate this by computing when the new curve starts beating PPSZ. With the log log n factors that appear in the real bound, that crossover point lands much farther away than in the simplified example:

// Finds the smallest k such that, for n = 2^k, the bound with a (log log n)^2
// factor in the exponent drops below PPSZ. We work with k = log2(n) to avoid
// overflowing JavaScript's Number. Illustrative: constants ignored.
function crossoverPoint() {
  const ppszRatio = Math.log2(1.307); // PPSZ exponent divided by n
  // New bound's exponent divided by n, as a function of k = log2(n).
  const newRatio = (k) => Math.log2(k) ** 2 / Math.sqrt(k);
  for (let k = 4; k <= 1e8; k *= 1.01) {
    if (newRatio(k) < ppszRatio) return `n ≈ 2^${Math.round(k).toLocaleString("en-US")}`;
  }
  return "above 2^100000000";
}

console.log(crossoverPoint());

Even in this constant-free version, the crossover point sits near n = 2 raised to about one million: a number of variables with hundreds of thousands of digits, far beyond any formula a computer will ever process. That is why the importance of the result is theoretical: it changes the map of what is possible, not the performance of your solver.

What About Cryptography? Is Your Data Safe?

This was the first question for a lot of people, and it makes sense: if an NP-complete problem got "easier", does cryptography go down with it?

Ryan Williams, one of the researchers invited to examine the result, answered directly in a statement reproduced in the Hacker News discussion: "In fact, one of the first things I wanted OpenAI to check is that no existing cryptosystems are compromised by the result." He added that, apparently, they are safe.

There are good reasons for that:

A small subexponential gain does not break keys. Schemes like RSA, elliptic curves, and post-quantum algorithms are already sized against known subexponential attacks. The strongest classical attack on RSA, the General Number Field Sieve, has been subexponential for decades.
Reductions do not preserve the gain. The preprint itself notes that time bounds of the form 2^o(n) do not transfer under general polynomial reductions. Converting a cryptographic problem into SAT usually inflates the number of variables a lot, and the gain evaporates.
The algorithm is galactic. Even if there were an efficient reduction, the crossover point is too far away to have any practical effect.

The Other Two Results: Kakeya and Yang–Mills

The October 26 announcement was not only about ETH. OpenAI presented three results at once.

Mathematics: local smoothing and Kakeya

The company claims its models produced a proof of Sogge's local smoothing conjecture for the Euclidean wave equation, in every spatial dimension from 2 upward. According to OpenAI, this would imply the Kakeya conjectures (maximal and dimension) and Stein's spherical restriction estimates, "throughout the interior of the conjectured range".

For context: in 2025, Hong Wang and Joshua Zahl published the proof of the Kakeya conjecture in three dimensions, considered one of the great results in analysis this decade. A proof covering all dimensions would be a huge leap. It is worth noting a tension in OpenAI's own words: the summary says "all dimensions", while the technical text restricts it to the interior of the conjectured range. In cases like this, the technical paper is what counts.

Physics: existence of quantum field theories

The third result is the most ambitious. OpenAI says its models produced a natural-language proof of the existence of Yang–Mills on September 9, 2026, and of quantum chromodynamics (QCD) on September 18, 2026, plus an extension to something the company calls a unified completion of the Standard Model.

The expert group following this work is led by David Gross, 2004 Nobel laureate in Physics for his work on the strong force, and includes Michael Douglas, Arthur Jaffe, Igor Klebanov, and Nikita Nekrasov. The full materials have not been released yet: according to the coverage, the group preferred to write its own interpretation before publishing.

An important point so you do not fall for the headline: the Clay Institute Millennium Prize Problem on Yang–Mills requires proving existence and the mass gap. OpenAI's claim covers existence; it does not claim the prize.

What Has Been Verified and What Has Not

This is the part that matters most, and the one headlines usually skip. As of October 27, 2026, none of the three results has independent confirmation.

The process OpenAI set up works with "shepherds": outside experts who organize groups to understand, check, and explain each result. For ETH, the group is made up of Russell Impagliazzo, Ramamohan Paturi, and Ryan Williams. The irony is obvious: Impagliazzo and Paturi are the very authors of the hypothesis the preprint claims to refute. In an open letter, they made it clear that their participation should not be read as certification of the result. It was at the group's request that OpenAI made the materials public.

The role of Lean

The Lean formalization is the strongest point of the ETH claim. Lean is a proof assistant: if the proof compiles, every logical step has been machine-checked. But there is a well-known trap, and it is worth understanding as a developer:

-- Illustrative sketch, NOT OpenAI's statement.
-- Lean guarantees the proof is correct with respect to the formal statement.
-- It does not guarantee the formal statement says what the paper says in plain English.
theorem algoritmo_subexponencial :
    ∃ alg : Algoritmo, ResolveKSAT alg ∧ TempoSubexponencial alg := by
  sorry -- the real proof would go here

If the definition of TempoSubexponencial or ResolveKSAT is subtly wrong, the proof compiles and still does not prove what was intended. That is why human reviewers still need to check whether the formalized statement matches the informal claim. In physics, no formalization is cited, and the materials are not even public.

What This Changes for Software Developers

In practice, in the short term, nothing changes in your code. Your SAT solver, your compiler, and your database will keep running the same algorithms tomorrow. But there are three lessons that apply to day-to-day work.

1. Conditional lower bounds are assumptions, not laws. Many people read "this problem has no algorithm better than X" without noticing the "assuming ETH" in the footnote. If you work with optimization, scheduling, or verification, it is worth knowing which hypotheses your "impossible" rests on.

2. Formal verification just got a huge use case. If AIs are going to produce proofs too long for humans to read line by line, tools like Lean become the trust filter. For devs, it is a sign that proof assistants and dependent types may leave the academic niche. If the topic interests you, it is also worth looking at how quantum computing is shaking other classical assumptions in the post about the encrypted qubits breakthrough in 2026.

3. Distrust headlines, trust process. The announcement was made by a company about its own product, and the reviewers were invited by it. That does not invalidate anything, but it is exactly why independent review matters. The right way to follow this is to wait for the report from Impagliazzo, Paturi, and Williams' group.

Outlook: AI as a Co-Author of Science

If the refutation of ETH holds up, 2026 will be remembered as the year an AI knocked down one of the central hypotheses of computing theory, an open problem since the late 1990s. And if it falls apart, the open review process happening right now will have shown the value of checking before celebrating.

Whatever the outcome, some things have already changed. The conversation moved from "can AI solve olympiad problems?" to "who reviews a proof that no human wrote?". The complexity community will need to rebuild part of the lower-bound map if the result is confirmed. And formal verification tools gained a spotlight few predicted two years ago.

For anyone who likes algorithms, this is a great moment to revisit the fundamentals: understanding SAT, reductions, and asymptotic notation has never been more useful for reading tech news. And if you like the idea of algorithms that explore huge search spaces, the post about genetic algorithms shows another way to attack hard problems.

Let's go! 🦅

📚 Want to Keep Up With What Is Coming?

This article covered OpenAI's claim that the Exponential Time Hypothesis is false, but the ecosystem changes every week and not everything becomes an article here.

On X I share what I am testing, the behind-the-scenes of my projects, and the news that shows up before it turns into a post.

Follow Me There

👉 Follow @jeffbruchado on X

💡 Daily content about development, career, and the tools I actually use