Subexponential Weighted Counting and Exact Optimisation

Introduction

The theorem of OpenAI

On 25 October 2026 OpenAI released a preprint [27] with a deterministic algorithm that, for every fixed $k \ge2$, counts the satisfying assignments of a $k$-CNF formula with $n$ variables and $m$ clauses in time

and polynomial space. Since $2^{O(n\log\log n/\sqrt{\log n})}=2^{o(n)}$, the exponential time hypothesis of Impagliazzo and Paturi [20], which asserted that 3-SAT needs time $2^{\Omega(n)}$, is false, and with it the strong hypothesis [21], the counting hypothesis #ETH [14], and the gap and nondeterministic variants. The algorithm is algebraic. It writes the count as a sum over the Boolean cube of a product of local polynomials, replaces every variable occurrence by a linear form in a parameter $T$ chosen so that at each of $Q$ sample points the factors separate into $r$ groups after a short list of integer measurements of the assignment has been fixed, recovers the Taylor coefficients of the resulting univariate polynomial at the sample points from Boolean substitutions, and interpolates back to $T=0$. The present paper owes its existence to that preprint, and every step of the algorithm that is used below is OpenAI’s.¹

What this paper adds

The counting routine of [27] is stated there for factors with rational coefficients, with the remark that it works over any commutative $\mathbb{Q}$-algebra. We take that remark seriously and run the algorithm over truncated polynomial rings $\mathbb{Q}[W]/(W^N)$. A factor may then be $W^{w(x)}$ for an integer weight function $w$ of a few variables, and the sum over the cube becomes a generating polynomial: its coefficient of $Wj$ counts the assignments of total weight $j$. One number has turned into a profile, and the profile contains an optimum. The cost of the change is nil in the exponent, and polynomial in $N$ elsewhere.

The technical statement is Theorem 5.3: for fixed $k$ and $c$, a system of at most $cn$ factors, each depending on at most $k$ of the $n$ Boolean variables and taking values in a commutative $\mathbb{Q}$-algebra $A$, is summed over $\{0,1\}^{n}$ in

The exponent is the one OpenAI obtain in their § 3–6 before the refinement that removes one logarithmic factor; we do not reproduce that refinement, because none of the consequences below needs it.

From Theorem 5.3 we deduce, with complete proofs:

• (i) for every fixed $k$ and $c$, the profile of a constraint satisfaction instance with $n$ Boolean variables and at most $cn$ constraints of arity at most $k$, that is the number of assignments satisfying exactly $j$ constraints for every $j$, in time $2^{O_{k,c}(\rho(n))}$ (Theorem 6.1); in particular the exact optimum of Max-$k$-SAT and of Max-Cut on sparse instances, together with the number of optimal solutions (Corollaries 6.2 and 6.4);

• (ii) the independence polynomial of every graph on $n$ vertices, hence its independence number, clique number, vertex cover number and the number of maximum independent sets, in time $2^{O(n(\log\log n)^2/(\log n)^{1/4})}$ (Theorem 6.7); the proof combines Theorem 5.3 with a branching rule on vertices of large degree whose cost we bound explicitly; the same branching carries any fixed number of vertex weights at once, which solves the knapsack problem with an arbitrary conflict graph and polynomially bounded weights, and its multidimensional form, exactly (Theorem 6.10, Corollary 6.11);

• (iii) Vertex Cover with parameter $k$ in time $2^{O(k(\log\log k)^2/(\log k)^{1/4})}+\operatorname{poly}(n)$, that is $2^{o(k)}$ up to a polynomial, through the kernel of Nemhauser and Trotter (Theorem 6.13); the lower bound $2^{\Omega(k)}$, which was a standard consequence of the exponential time hypothesis [9 Theorem 14.6], therefore fails;

• (iv) for every fixed $\Delta$, the density of states of the Ising model with integer couplings and fields, and of the $q$-state Potts model, on graphs of maximum degree $\Delta$ with $n$ vertices, in time $O_{\Delta,q}(\rho(n))$ (Theorem 6.18); every partition function and every ground state follows;

• (v) the minimum dominating set and the matching polynomial of a bounded-degree graph, the permanent of a sparse integer matrix, and the minimum hitting set and the maximum split of a sparse set system with sets of bounded size, in time $2^{O(\rho(n))}$ (Theorems 6.20 and 6.21);

• (vi) for fixed domain size and arity, every sparse constraint system over a finite domain, hence every partition function $Z_A(G)$ of a fixed symmetric rational matrix $A$ and the number of homomorphisms into a fixed graph, on bounded-degree graphs, in time $2^{O(\rho(n))}$ (Theorem 6.15, Corollary 6.16);

• (vii) the satisfying assignments of a sparse $k$-CNF formula of each Hamming weight, and those whose weight lies in a prescribed residue class, in time $2^{O(\rho(n))}$ (Corollary 6.3, Proposition 6.23);

• (viii) further families worked out in § 7: several linear statistics of the solutions of a sparse constraint system at once, with equations and congruences imposed (Theorem 7.1); Max-$k$-Lin modulo $p$, Max-$q$-Cut and balanced $q$-partitions (Corollary 7.4); on bounded-degree graphs, $f$-factors, even and odd subgraphs, orientations with prescribed indegrees, proper edge colourings and nowhere-zero flows by weight (Theorem 7.5), and the Tutte polynomial on every hyperbola $(x-1)(y-1)=q$ with $q$ a positive integer, which contains

the chromatic and flow polynomials at $q$ and the $q$-state Potts model (Theorem 7.10); the weight enumerator, the minimum distance and maximum-likelihood decoding of a binary code with sparse parity checks (Theorem 7.12); matchings, transversals and colourings of bounded-degree hypergraphs (Theorem 7.14); the weighted output profile of a linear-size circuit of bounded fan-in (Theorem 7.15); and the optimum and the number of optimal solutions of a 0-1 or bounded integer program with $O(n)$ rows, each involving a bounded number of variables with coefficients of any size, and a fixed number of further dense rows with polynomially bounded coefficients, which contains exact cover with bounded element frequency and the partially ordered knapsack problem (Theorem 7.17, Corollary 7.18), all in time $2^{O(\rho(n))}$;

(ix) the same for systems whose density grows with $n$: with parameters that follow the ratio $c$ of factors to variables, the exponent is $O(n g(\theta))$ with $\theta= c_k\sqrt{\log\log n}/\log n$ and $g(x) = x\log^{3/2}(1/x)$ (Theorems 7.19 and 7.20), so that the maximum cut, the maximum bisection and the Ising and Potts ground states of a graph of average degree $d(n)$, the exact optimum of Max-$k$-SAT with $d(n)n$ clauses and that of an integer program with $d(n)n$ sparse rows are found in time $2^{o(n)}$ whenever $d(n) = o(\sqrt{\log n/\log\log n})$ (Corollaries 7.21 and 7.26); and, through the complement, the cut profile of every graph whose complement has that many edges, a class that contains graphs with $\Theta(n^2)$ edges (Corollary 7.22), and more generally the cut profile of every graph that differs in that many pairs from a blow-up of a graph on $o(n/\log n)$ vertices, or from a weighted graph whose weights are a quadratic form in $s$ vertex weights with $s\log(n\Omega) = o(n)$ (Theorem 7.23 and Corollary 7.24); a count shows that these classes contain almost no graphs (Remark 7.25);

(x) $k$-SAT lies in the class SE of problems solvable in time $2^{\varepsilon n}$ poly for every $\varepsilon> 0$, by the sparsification lemma of Impagliazzo, Paturi and Zane [21], and therefore every problem of the class SNP of Papadimitriou and Yannakakis [29] lies in SE (Theorem 8.4).

Items (i)–(ix) concern problems for which no $2^{o(n)}$ algorithm was known and for which such an algorithm was excluded under the exponential time hypothesis by standard reductions. The best exact algorithms for the maximum independent set run in time $2^{0.1996n}$ [XN17], for Max-Cut in time $2^{\omega n/3}$ where $\omega$ is the exponent of matrix multiplication [35], and for the permanent and the perfect matchings of sparse graphs in time $2^{n-\Omega(n/\Delta)}$ [12]; each of these bounds is exceeded here asymptotically.

What this paper does not claim

The algorithm counts sums of products of local factors over a cube of dimension $n$ and its running time is subexponential in $n$. Two features limit its reach, and they are stated here so that no reader expects more. First, the exponent is $o(n)$ and not $n^{o(1)}$. A polynomial-time reduction from an NP-complete problem to 3-SAT multiplies the number of variables by a polynomial, so the algorithm says nothing about P versus NP, and nothing here bears on that question. Second, the number of factors and the total degree of their product must be $O(n)$, or $o(n\sqrt{\log n}/\log\log n)$ after Theorem 7.20, after a branching step that fixes $O(n/\log n)$ variables; Remark 7.27 shows that the runtime itself cannot go beyond total degree of order $n\log n$. Max-Cut on general graphs with $\Theta(n^2)$ edges, the chromatic and Tutte polynomials as polynomials in $q$ (as opposed to their values at a fixed positive integer $q$, which Theorem 7.10 does give on bounded-degree graphs), Orthogonal Vectors, 3SUM and All-Pairs Shortest Paths need either $\Theta(n^2)$ constraints or reductions that multiply the variable count, and they are untouched. The paper contains no partial result on any of these problems.

Organisation

Section 2 fixes notation and the model of computation over an algebra. Sections 3 and 4 reproduce the summation routine and the construction of the replacement forms. Section 5 proves Theorem 5.3, including the branching on frequent variables and the bit-complexity bound over $\mathbb{Q}[W]/(W^N)$. Section 6 proves items (i)–(vii), Section 7 proves items (viii) and (ix), Section 8 proves item (x), and Section 9 records what the method does not give. Appendix A describes exact-arithmetic checks of the extended algorithm on small instances and of the finite inequalities behind Section 7.9; no statement of the paper depends on them. The author’s earlier work on algorithmic structures in geometric and topological settings [4, 5, 6] is unrelated in method but shares the aim of making a computation explicit enough to be verified line by line.

A word on the constants. The parameters of Lemma 4.7 become admissible only when $\sqrt{\log n}$ exceeds a large multiple of $(\log\log n)^2$, that is for $n$ beyond any practical size; the same is true of OpenAI’s algorithm, and Figure 1 shows where the three costs of the routine settle; Theorem 7.19 asks for $\log n \ge2^{30}\log\log n$ at the least. The theorems are statements about asymptotic complexity, and the paper does not present them as anything else.

Preliminaries

Notation

For an integer $Q \ge1$ we write $[Q] = \{1,\ldots,Q\}$. Boolean assignments are vectors $x \in\{0,1\}^n$, also read as vectors in $\mathbb{Q}^n$. For $S \subseteq[n]$, $x|_S$ is the restriction and, for $\xi\in\mathbb{Q}^S$, $\widetilde{\xi} \in\mathbb{Q}^n$ is the extension of $\xi$ by zero. The unit vector at $v$ is $e_v$, and $\mathbf{1}_U$ is the indicator vector of $U \subseteq[n]$. Logarithms are to base 2 unless written $\ln$. For $n \ge20$ put

so that $\lambda= \Theta(\log n)$ and $\nu= \Theta(\log\log n)$.

Algebras and factors

Throughout, $\mathcal{A}$ is a commutative $\mathbb{Q}$-algebra with identity. The two cases of interest are $\mathcal{A} = \mathbb{Q}$ and the truncated polynomial ring

whose elements are polynomials of degree less than $N$ with rational coefficients, added coefficientwise and multiplied with the terms of degree at least $N$ discarded. An addition in $\mathcal{A}_N$ costs $N$ rational additions and a multiplication costs at most $N^2$ rational multiplications and additions. More generally, for integers $N_1,\ldots,N_s \ge1$ we use

a $\mathbb{Q}$-vector space of dimension $N = N_1\cdots N_s$ with the monomials $W_1^{j_1}\cdots W_s^{j_s}$, $0 \le j_i < N_i$, as a basis; its arithmetic costs the same as that of $\mathcal{A}_N$ with this $N$. Both are commutative $\mathbb{Q}$-algebras, and so is the group algebra $\mathbb{Q}[W]/(W^m-1)$ of the cyclic group of order $m$, which appears in Section 6.

A factor system on $n$ variables is a finite index set $\mathcal{F}$ together with, for each $f \in\mathcal{F}$, a scope $I_f \subseteq[n]$ and a polynomial $\Phi_f \in\mathcal{A}[Y_v:v \in I_f]$. We write