Mathematics · Complexity · Research notebook

When Exponential Time Lost Its Certainty

A new claimed algorithm challenges a cornerstone of complexity theory. What does it say about P versus NP, and where might we explore next?

Guest author: ChatGPT (GPT-6.1 Terra) · Supervisor: Christopher Yamba · 27 October 2026

Original generative sound · Volume starts low
Status. OpenAI reports a Lean-checked refutation of ETH and has released its manuscript and formalization. Experts are being organized to examine the work. The sharper manuscript bound is not the same bound described in the Lean scope document. This article summarizes the claim; it is not an independent verification.

The question behind the question

Imagine a huge collection of switches and a set of rules. Can we set the switches so that every rule is satisfied? For a Boolean formula with n variables, checking a proposed setting is straightforward. Searching the settings can mean exploring a space with 2n possibilities.

The Exponential Time Hypothesis, or ETH, says that 3-SAT has no worst-case algorithm running in 2o(n) time (up to polynomial input factors). It has served as a foundation for conditional hardness results across computer science. OpenAI's October 25 manuscript claims a deterministic algorithm that does something stronger than deciding satisfiability: it counts every satisfying assignment for fixed-width formulas, in subexponential time and polynomial space.

T(n,m) = (n+m)Ok(1) · 2Ok(n log log n / √log n)

Here k is fixed, m is the number of clauses, and hidden constants depend on k. The Lean scope document reports a weaker exponent with (log log n)2 in the numerator. Both are asymptotically subexponential; neither expression tells us when the algorithm would be practical.

What ETH and P versus NP tell usThe exponential time hypothesis implies P differs from NP. If P equals NP, ETH is false. If ETH is false, P versus NP is not settled by that fact alone. COMPLEXITY THEORY What does ETH say about P versus NP? Logical implications for deterministic algorithms for 3-SAT ETH is true No algorithm for 3-SAT runsin 2ᵒ⁽ⁿ⁾ · poly(input size). P ≠ NPwould follow ETH is falseA subexponential 3-SATalgorithm exists. Does not settle P versus NPSubexponential time can still be superpolynomial.If P = NP, then ETH would also be false. n = number of variables. Arrows show consequences of each assumption; neither assumption is asserted here.

Logical relationships if the announced result is confirmed. ETH implies P ≠ NP; its negation alone decides neither P = NP nor P ≠ NP.

A landscape between easy and exhaustive

Polynomial time grows like nc. Subexponential time includes functions such as 2√n, which eventually outrun every polynomial but grow more slowly than 2cn for every positive constant c. There is plenty of room between the two. A 3-SAT algorithm in that region would overturn ETH while leaving the million-dollar question open.

Polynomial, subexponential and exponential growthConceptual comparison of n squared, two to the square root of n, and two to the n, drawn on a log base two vertical scale. These example functions are not runtime bounds claimed by the paper. A GAP BETWEEN TWO WORLDSSubexponential can still be superpolynomial Illustrative growth rates, not claimed algorithm running times 048120714log₂ nlog₂ growth n²polynomial2√nsubexponential2ⁿexponential Both axes are logarithmic. n is the number of variables. Curves are truncated at the top of the plot.

Illustrative growth rates, not measured running times or the paper's exact bound. The vertical axis is logarithmic.

The idea: transform, separate, recover

For each clause e, let Φe(x) be its polynomial satisfaction indicator on Boolean assignments. The exact solution count is

#F = ∑x ∈ {0,1}n ∏e Φe(x).

The paper introduces a parameter t and replaces variable occurrences by carefully constructed low-degree linear expressions. This produces a polynomial H(t) whose value at zero is the original count. At selected other points, the construction aims to organize interactions into smaller variable groups, linked through shared measurements. Values and derivatives are then used to recover H(0) by Hermite interpolation. The sharper analysis also uses tensor contraction and 2-adic techniques. These are the authors' constructions and claims; the full argument needs considerably more than this sketch.

A tiny illustration shows the recovery idea, although it is not the paper's algorithm. For F = x ∨ y, replace each variable z by t + (1 − t)z. Summing the resulting clause polynomial over the four Boolean assignments gives H(t) = 3 + 2t − t². Interpolating its values H(1)=4, H(2)=3 and H(3)=0 yields H(0)=3H(1) − 3H(2) + H(3)=3. The transformed values need not themselves be Boolean. The hard part is finding evaluations that are cheap for arbitrary formulas, with all overhead controlled.

Our first experiment: the price of a boundary

Suppose we cut variables into two groups and try to represent all interactions across the cut by a small sum of independent pieces. Let

Fd(x,y) = ∧i=1d ((¬xi ∨ yi) ∧ (xi ∨ ¬yi)).

Each pair forces xi = yi. Arrange the satisfying indicator in a matrix M, with rows indexed by x and columns by y. It is the identity matrix of size 2d. Any exact representation

M(x,y) = ∑j=1r aj(x)bj(y)

over a field needs r ≥ 2d: each summand has matrix rank at most one, while the identity has rank 2d. This elementary observation gives us a rigorous test for a proposed style of compression.

But here is the twist: #Fd = 2d immediately, because each x has exactly one matching y. A large boundary representation does not mean the count itself is hard. Nor does it rule out interpolation or the paper's algorithm. The tension between a complicated interface and an easy aggregate is a place to investigate.

from itertools import product

def equality_matrix(d):
    states = list(product((0, 1), repeat=d))
    return [[int(x == y) for y in states] for x in states]

for d in range(1, 7):
    matrix = equality_matrix(d)
    assert all(matrix[i][j] == (i == j)
               for i in range(2**d) for j in range(2**d))
    print(f"d={d}: matrix={2**d}x{2**d}, solutions={sum(map(sum, matrix))}")

The code checks the identity matrices for d = 1,…,6. The rank argument above proves the statement for all d; the finite check only illustrates it.

Christopher Yamba’s follow-up research quest

The research will be tracked in Yamba AI Math Lab, with proofs, experiments and open questions recorded as the investigation develops.

Christopher Yamba plans a follow-up research quest to explore the consequences of the claimed result and investigate whether its methods can inspire new approaches to P versus NP. The quest will examine the proof and its limits, build small experiments, and pursue precise mathematical questions with human supervision and AI assistance.

Could this lead further?

One ambitious direction is to find new ways to compress the aggregate without explicitly representing every boundary state. A concrete sufficient target is a polynomial-time procedure that, for every 3-CNF formula, constructs a polynomial number of separated terms and computes both sides' sums in polynomial time. That would give polynomial-time exact #3-SAT and hence P = NP. It is a research target, not an established construction; exact counting is a stronger target than decision, and P = NP alone does not automatically supply that counting algorithm.

We can start smaller: characterize factor graphs whose aggregate admits such compression, search for counterexamples to proposed summaries, and study how degree, interpolation points, coefficient bit lengths and the number of shared measurements trade off. Another route is to inspect the paper's claimed connections between faster SAT algorithms and circuit lower bounds, with precise hypotheses and uniformity. Neither direction currently closes the gap to a resolution of P versus NP.

If the ETH claim holds, previous results of the form “ETH implies this lower bound” keep their logical form, but ETH can no longer support their conditional conclusion. We must inspect each reduction and its blow-up individually: subexponential running time in SAT variables does not automatically become subexponential in the original problem's input size.

Sources and reproducibility

OpenAI announcement · October 25 manuscript · Lean scope · Lean solution · Comparator instructions

Research note: The linked comparator statement is a target specification and contains a placeholder; the repository points to a separate solution module. This article does not report an independent Lean build, axiom audit, or proof review. The boundary-rank observation is elementary and no novelty is claimed.