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
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.
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.
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.
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
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
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
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.