WorksComputer Science
Limits and Constants of OpenAI's Claimed ETH Refutation
Abstract
A recent OpenAI preprint claims a deterministic algorithm that counts the satisfying assignments of a -CNF formula in time , and at bounded clause density, which would refute the Exponential Time Hypothesis. The headline bound is proved by tensor contraction; the body develops an interpolation algorithm with the weaker exponent . This note does four things. First, it explains the interpolation algorithm in plain terms. Second, it asks how large must be for the bounds to bite. The preprint states no constants, so we treat the hidden constant as a parameter: the general bound beats the of brute force only beyond for , for and for . We then extract the constants from the tensor-contraction proof: for every input with clauses at bounded density, the running time it certifies stays above unless , and on random 3-CNF at the satisfiability threshold unless . So the bounds are subexponential as , but the proof certifies no speed-up over brute force for any input of bounded density that could ever be written down. Third, for the clause-product form of the interpolation algorithm we prove limits in a cost model matching the preprint's evaluation. By a short algebraic lemma, polynomial cost needs components of variables with per-point evaluation, or primal treewidth with dynamic programming over the groups. So the scheme costs at treewidth , with high probability on random 3-CNF above clause density 3, and even on trivially countable path formulas. We explain why the preprint's sharper routes escape these limits. Fourth, we report experiments.
Introduction
The Exponential Time Hypothesis (ETH) of Impagliazzo and Paturi [35] states that 3-SAT on variables needs time for some . Together with the sparsification lemma [36] it underlies a large part of fine-grained complexity [52]. On 17 October 2026 OpenAI posted a preprint [44], revised on 25 October, whose Theorem 1.1 states that #-SAT can be solved deterministically in time and polynomial space, and in time when . This refutes ETH and its counting version #ETH [24]. The preprint uses natural logarithms throughout. Its Appendix D proves both bounds by contracting Boolean tensor networks. The body of the preprint develops an interpolation algorithm (its Proposition 6.4) with the weaker exponent
At the time of writing the claim is under independent review. We take the preprint’s proofs at face value and do not assess their correctness.
The interpolation algorithm comes in two forms. The clause-product form (Sections 2.1–2.8 of the preprint) multiplies clause polynomials of a formula in which every variable occurs at most three times, reached by sparsification and variable copies. For general -CNF the preprint derives only from it (its Section 2.8), but on formulas of bounded density, where variable copies alone give variables, it yields . The parity form (Section 2.9 and Theorem 2.2) replaces clauses by sparse polynomial equations over and achieves in general. Our contributions are as follows.
A plain-language account (§ 3). We explain the interpolation algorithm step by step, with a three-variable example in which every quantity can be checked by hand, and we say which parts of the sixty-page proof carry the weight and which are engineering.
The constants (§ 4 and Appendix § 14). The preprint states no constants. We tabulate where its bounds beat brute force as a function of the hidden constant, and we extract the constants of the tensor-contraction proof from its Appendix D. For every input of bounded density, the running time that proof certifies is above unless .
A vanishing-product lemma (Lemma 6.2). In the clause-product scheme, each occurrence of a variable carries a polynomial “own coefficient” that equals at ; their product has degree at most the degree up to which the recovery is exact, so it cannot vanish to high order at every evaluation point. Hence at some point at most occurrences lose their own variable, where is the Taylor order used there.
Necessary conditions for polynomial cost (Theorems 7.1 and 7.2), in a cost model that charges what the preprint’s evaluation pays (§ 5). At that point the formula’s primal treewidth is at most , where is the group size and the treewidth of the groups’ interaction graph. Polynomial cost therefore forces primal treewidth , and with the preprint’s per-point evaluation and bounded occurrence it forces the formula to be a union of -variable pieces.
Barriers (§ 8). In the same model, the clause-product scheme costs on formulas of treewidth ; w.h.p. on random 3-CNF with , , both after the preprint’s reduction to bounded occurrence and after its sparsification step; and with the preprint’s evaluation even on path formulas.
These results say nothing against the preprint’s subexponential bounds. The limits concern the clause-product scheme only. The parity form and the tensor contraction fall outside them, and we explain why (§ 5.1). For the clause-product scheme on expanding inputs of bounded density, the cost lies between and , and whether it is near either end is open (§ 9).
Related work
ETH, SETH and exact algorithms. ETH and the Strong ETH were formulated by Impagliazzo and Paturi [35]; sparsification [36] with its quantitative form by Calabro, Impagliazzo and Paturi [17, 16] transfers ETH to many problems, and its counting-preserving form [24] gives #ETH.
Exponential algorithms for -SAT include randomised local search [48] and PPSZ [45], with Hertli’s analysis [30], biased PPSZ [29] and Scheder’s improved analysis [47]. For counting, Dahllöf, Jonsson and Wahlström [23] and Wahlström [53] gave exponential-time bounds for -SAT and -SAT, and Kutzkov [38] recently improved the bound for -SAT. Fine-grained complexity is surveyed in [52].
Algebraic and interpolation methods. Counting through polynomial identities goes back to Valiant’s permanent [51]; inclusion–exclusion [9], algebraic sieving for paths and packings [37, 54] and determinant sums [8] made it a design tool. The polynomial method of Williams [55] and its descendants [1] give super-polylogarithmic savings for many problems; for systems of polynomial equations over it yields -type algorithms [42, 10, 25]. Curticapean’s block interpolation [22] is a counting framework for tight lower bounds. The preprint [44] combines a one-parameter deformation of clause inputs with Hermite interpolation, expander-code parity checks and sparsification (we describe it in § 3), and proves its sharpest bounds by a recursive contraction of Boolean tensor networks with two-adic Hermite recovery.
Treewidth and counting. Model counting is fixed-parameter tractable in the treewidth of the primal or incidence graph [26, 46]; see [11] for treewidth in general and [12, 13, 28] for the upper- and lower-bound heuristics used in our experiments; exact counters based on component caching, such as sharpSAT [49] and d4 [40], are the practical standard. Random graphs above the giant-component threshold have linear treewidth [27, 41], and linear width of random CNF is a standard consequence of their expansion; we include a short self-contained proof of the form we use (Lemma 8.2).
Barriers for methods. Our results are barriers for a method, not for a problem, in the spirit of the limits of the laser method for matrix multiplication [5, 4, 3, 18]. In proof complexity, expansion is the common source of lower bounds for resolution [19, 7] and the polynomial calculus [6, 2]; our treewidth condition plays the same role for the clause-product scheme. Restricted-model lower bounds also underlie the low-degree method for average-case problems [34, 39], whose limits have been probed by counterexamples built from decodable codes [32, 14].
Benchmarks. The SATLIB uniform random 3-SAT families [33] sample the satisfiability threshold near [43, 21].
The OpenAI argument in plain terms
This section is for readers who know what a satisfiability problem is and little else. It uses no algebra beyond school-level polynomials. It describes the preprint’s interpolation algorithm; the small example is ours. Specialists can go straight to § 3.10, which restates it in the preprint’s terms.
The problem: counting good settings
Picture on/off switches and a list of rules, each mentioning at most three switches, such as “switch 1 is on, or switch 2 is off, or switch 3 is on”. A setting of all the switches is good if it obeys every rule. The task is to count the good settings; counting is at least as hard as deciding whether one exists.
The obvious method tries every setting. There are of them, which for 100 switches is about , far beyond any computer. The Exponential Time Hypothesis is the belief that nothing fundamentally better is possible: that the running time must grow like for some fixed , as if a fixed fraction of the switches always had to be tried exhaustively. The preprint claims an algorithm whose running time grows more slowly than that.
Why splitting helps
Suppose the switches fell into two teams of 50, and every rule mentioned switches of one team only. Then we could count the good settings of the first team (at most to try), count those of the second, and multiply, because every good setting of one team combines with every good setting of the other. That is settings to try instead of , about a million billion times fewer. More, smaller teams would be better still.
Hard puzzles typically do not split like this. In a random puzzle the rules tie the switches into a well-knit net: however the switches are divided into teams, a large share of the rules mention switches of two different teams. Graphs of this kind are called expanders.
The idea: a dial that rewires the rules
First, a way to count. Give each rule a score for each setting: 1 if the setting obeys it, 0 if not. Multiply the scores of all the rules, which gives 1 for a good setting and 0 for any other, and add up over all settings. The total is the number of good settings. We call this the counting recipe.
The preprint does not split the puzzle. It builds a whole family of related puzzles, one for each position of a dial , with three properties.
At the puzzle is the original one, so the recipe gives the count.
At certain other dial positions the puzzle does split into small teams, apart from a little controlled leakage, described in the next subsection.
The number that the recipe produces depends on the dial in a very regular way: as a polynomial in , the kind of curve that can be reconstructed from a few readings.
The rewiring works like this. A rule does not read its switches directly; it reads blends of switches whose mix depends on the dial. In one rule, “switch 2” might become “ times switch 2, plus times switch 3”. At this is switch 2 itself. At it is switch 3, and that rule no longer mentions switch 2 at all, so the link the rule made through switch 2 is gone. Different rules can be rewired differently.
At most dial positions the blends are not simply 0 or 1, so the scores are not either, and the number the recipe produces there does not count anything. It is just a number. That does not matter, because all we need are points on the curve.
Leakage through summaries
At a single dial position it is impossible to cut every link of a hard puzzle. The preprint lets each team publish a few summaries of its switches, such as “how many switches of team 3 are on”, and lets the rules of other teams read those summaries instead of the switches themselves (Figure 1). A summary takes only a few possible values, between 0 and 10 say.

Figure 1. The split at one dial position. Fixing the value of every summary makes the teams independent, so each team can be counted on its own; the price is the number of possible combinations of summary values.
To produce the number at that dial position, go through every combination of summary values. For each combination the teams are independent again, so count each team on its own and multiply. The price is the number of combinations of summary values that have to be gone through.
Reading the answer off the curve
The number we want is the value of the curve at , where nothing splits. We can compute the curve only at the special dial positions where the puzzle does split. But a polynomial is rigid. A straight line is fixed by two of its points; a curve of degree by points; and fewer points will do if at each one we also know the slope, the rate of change of the slope, and so on. So the recipe is: compute the curve at enough splitting positions, reconstruct it, and read off its value at . That value is the exact count.
The degree of the curve grows with the number of switches and with how strongly the blends depend on the dial. To keep the number of dial positions small, the preprint uses slopes and higher rates of change at each position. These are the expensive part. The split holds exactly at the chosen position, not slightly away from it, so the rates of change need a separate trick, whose cost grows quickly with how many of them are wanted.
A worked example
Take three switches and two rules: “switch 1 or switch 2” and “switch 2 or switch 3” (Figure 2). Of the eight settings, five are good: the four with switch 2 on, and the one with switch 2 off and switches 1 and 3 on. The two rules share switch 2, so the puzzle does not split.

Figure 2. The worked example. Circles are switches, boxes are rules. (a) With the dial at 0 the two rules share switch 2. (b) With the dial at 1 the second rule has been rewired to read switch 3 instead, so the puzzle splits into the blue team {1, 2} and the green team {3}, and the recipe’s number is a product of two small counts. (c) The recipe’s number is the straight line ; its value and slope at the split position determine its value 5 at , which is the count of good settings.
Rewire only the second rule’s reading of switch 2, to “ times switch 2, plus times switch 3”. Running the counting recipe now gives a number that depends on the dial, namely .
At it is 5, the true count.
At the second rule reads “switch 3 or switch 3”, which mentions only switch 3. The puzzle splits into the team , whose rule has three good settings, and the team , whose rule has one. The recipe gives , computed as a product of two small counts.
The curve is a straight line, so one more fact at fixes it: its slope there, . Going back one unit along a line of slope from height 3 reaches height 5 at : the count.
Two features of this example matter later. First, the slope is where the cost hides: the rate at which the rewired reading changes is “switch 3 minus switch 2”, which involves both teams again. The preprint’s trick for rates of change exists to handle exactly this. Second, the rewired reading contains switch 2 with weight . That weight is 1 at and 0 at , where the link is cut. A weight that is a polynomial starting at 1 can be zero at only a few dial positions. This is the fact our limits rest on.
Three costs, balanced
At each splitting position there are three kinds of work: counting inside one team, which doubles with every switch added to a team; going through all combinations of summary values; and computing the rates of change, whose cost grows with how many are needed there. The three pull against each other. Smaller teams need more summaries; fewer summaries or fewer dial positions need more rates of change. The technical heart of the preprint is a construction that keeps all three costs well below at the same time, with teams that are a shrinking fraction of all the switches.
The result is a running time of , where grows without bound, but very slowly: roughly like the square root of the number of digits of , divided by a smaller correction. Because grows without bound, no fixed fraction of the switches has to be searched exhaustively, and that is what refutes the Exponential Time Hypothesis. An appendix of the preprint proves a somewhat better bound by a different method, which combines small tables of numbers along a network instead of reading a curve at a few dial positions.
How large must a puzzle be before any of this helps? A bound of the form “at most a constant times this” says nothing until the constant is known, and the preprint gives none. If its hidden constant were 3, its general bound would beat trying every setting only for puzzles with more than about switches, far more than the roughly atoms in the observable universe. We traced the constants through the preprint’s appendix. For puzzles with at most a few rules per switch, the guarantee it proves beats trying every setting only once the number of switches and rules together has more than a billion binary digits: a number that no computer could write down. Section 4 gives the table and the derivation. The result is about how running time grows as puzzles become infinitely large, not about counting any actual puzzle faster.
From special puzzles to all puzzles
The above needs every switch to appear in at most three rules, which keeps the degree of the curve low. Any puzzle can be brought to that form without changing its count, in two steps. An established technique called sparsification [36, 17, 24] splits it into many puzzles, each with few rules. Then each switch that appears in many rules is replaced by several copies, chained by rules that force all the copies to agree [50]. A sharper version in the preprint replaces the rules by short “parity checks”, equations that only ask whether an even number of rules are broken, built from error-correcting codes; we do not describe it in detail.
Why it cannot go all the way
To split a hard puzzle at some dial position, many rules must stop mentioning switches they originally mentioned. Each such cut means that a weight starting at 1 has dropped to 0 at that position, and each weight can do that at only a few positions. Meanwhile the reconstruction needs enough positions, or enough rates of change, to pin the curve down. § 6 turns this into a short proof: at some position only a few links can be cut. A tangled puzzle then cannot split there, and that position is expensive. For random puzzles the cost is at least (§ 8); with the preprint’s way of combining teams, even a simple chain of rules costs at least (§ 7).
These limits apply to the method as described in this section, where every rule is scored directly. The parity-check version and the network method of the preprint’s appendix work differently, and our limits do not cover them (§ 5.1).
The same, in the preprint’s terms
Write each clause as its satisfaction polynomial , equal to 1 when the clause is satisfied and 0 otherwise; for , . Then
The dial replaces each input of clause by a linear form with polynomial coefficients of degree at most and , giving
with and when every variable occurs at most three times. At each point of a set of nonzero points, an -design partitions the variables into groups of at most variables, assigns each clause to a group, and gives each group an integer measurement matrix. There are at most measurement rows in total, shared by all clauses, and each row has coefficients whose absolute values sum to at most . Every clause may depend on groups other than its own only through their measurements. We say that an occurrence loses its own variable at when the coefficient of in is zero; this is how a link is cut in the language above, and measurements are the second way of removing a link. is recovered by Hermite interpolation from derivatives at each point; the derivatives are computed by inclusion–exclusion over sets of at most variables. Per point the cost is, up to polynomial factors,
with logarithm . The design construction (Section 2.7 of [44]) achieves
so all three terms in the bracket are and the exponent is . General -CNF is reduced to the bounded-occurrence case by counting-preserving sparsification, OR-gate splitting of long clauses, and copies tied by Tovey’s implication cycle . This is the clause-product form. The parity form (Section 2.9 and Theorem 2.2 of the preprint) applies the same interpolation to sparse polynomial equations over , obtained from parity checks on short lists of clauses, and multiplies their integer lifts in a truncated algebra that discards terms divisible by a high power of two. It gives for every -CNF (Proposition 6.4 of the preprint).
| general: for | bounded density: for | |
| 1 | every | |
| 2 | ||
| 3 | ||
| 5 | ||
| 10 | ||
| 20 | ||
| 50 | ||
| (not extracted) | (Proposition 4.1) |
Table 1. Where the bounds of Theorem 1.1 of [44], with constant in the exponent and natural logarithms, fall below the of brute force; polynomial factors are ignored. The last row is the constant of the tensor-contraction proof for random 3-CNF at density 4.26 (Proposition 4.1). Computed by experiments E0 and E5 (Appendix § 15).
How large must be? The constants
All bounds in the preprint hide their constants in , and all its logarithms are natural. A subexponential bound with beats the of brute force only once , so where that happens depends entirely on .
With a hidden constant. Write . The general exponent of Theorem 1.1 satisfies if and only if . The function decreases up to and increases after it, so for it has a last zero , beyond which the general bound beats brute force for good. For it is positive for every . The bounded-density exponent satisfies if and only if . Table 1 lists the thresholds. Polynomial factors and the best known #3-SAT algorithms, which are much faster than , would push every entry further out.
The constants of the proof. The preprint proves Theorem 1.1 with a recursive contraction of a Boolean tensor network (its Theorem D.1). For inputs of bounded density, and more generally whenever , the network has one vertex per clause and equality trees joining the occurrences of each variable, with every edge subdivided; it has edges, and for a 3-CNF in which every variable occurs at least three times. The recursion is driven by explicit parameters: , , groups, , and retained valuation levels at the root. Tracing them gives the following (proof in Appendix § 14).
Proposition 4.1. Consider such an input with occurring variables. If the root call of the recursion is active, which requires , the running time that the proof of Theorem D.1 of [44] certifies is at least , where
Otherwise the algorithm uses direct summation, which costs at least . Consequently the certified running time is at least unless . For a 3-CNF with in which every variable occurs at least three times, it is at least unless ; in the form of Theorem 1.1 this is .
Three remarks put this in context. First, the bound counts only the root of the recursion; the deeper levels add about 15% to the exponent if every level shrinks by exactly the guaranteed factor (experiment E5). Second, the root’s count is not merely slack in the analysis. When the number of mode variables in (D.13) of the preprint is attained, it estimates the number of “mode tuples” the algorithm enumerates, and on small cases the exact number of tuples is within 10–13% of the estimate in the exponent, with the ratio rising towards 1 (experiment E5). Third, the preprint proves its estimates only for above an unstated threshold, and handles smaller sizes by direct summation. One of its stated parameter inequalities, in (D.5), holds at the root only when , that is . For inputs of bounded density, Theorem 1.1 is therefore a statement about ; its proof certifies no speed-up over brute force for any input that could be written down.
For the parity branch, used when , the constant also depends on the constant of Section 6 of the preprint, which is not made explicit, and we do not extract it. For the interpolation exponent with constant one, Proposition B.2 in Appendix B gives the crossover: about with natural logarithms, and with base-2 logarithms.
The clause-product scheme, abstracted
Let be a CNF over with clauses of at most literals, the variable set of clause , and its occurrences, . Let bound the number of occurrences of a variable. The incidence graph joins each clause to its variables; the primal graph joins two variables that share a clause.
Definition 5.1 (Clause-product interpolation scheme). A scheme for consists of the following.
(a) Deformation. For each occurrence a vector of degree at most with ; as in (3). Its own coefficient is , a polynomial of degree at most with . Since , .
(b) Recovery. A finite set , orders for , and a linear functional on Hermite data with for every of degree at most .
(c) Designs. For each : a partition of into groups ; a group for each clause; a subspace (the span of the measurement rows) for each group, such that for every clause , every and every group ,
Write , , and for the number of measured groups (). The interaction graph has the groups as vertices; for each clause the groups for some form a clique. Let .
The clause-product form of the preprint’s interpolation algorithm (its Sections 2.1–2.8) is an instance, with the row space of its integer measurement matrix and Hermite interpolation with (Section 2.5 of [44]). We say that loses its own variable at if .
What the definition does not cover
Two hypotheses carry the argument: the degree bound in (a), which holds because the number of occurrences is at most the degree of the clause product, and recovery that is exact for every polynomial up to that degree in (b). The preprint’s sharper routes break them.
The parity form (Theorem 2.2 and Proposition 6.4 of [44]) multiplies one factor per parity test, with one replacement form per test–variable incidence. The total number of incidences is (proof of its Theorem 2.2), but the product is formed in a truncated algebra and Hermite recovery is exact only up to degree (its (5.5) and (3.2)). The product of own coefficients then has degree up to , far above the degree of exactness, and the proof of Lemma 6.2 fails. The conclusion fails too in general: when is much larger than the exactness degree, can exceed .
The tensor contraction (Appendix D of [44]) uses “tapered” Hermite recovery over a two-adic ring: the multiplicity at a node depends on its two-adic valuation, and is recovered only modulo , for polynomials satisfying integrality conditions. This is not a functional exact for all polynomials of bounded degree, so it violates (b). It also replaces inclusion–exclusion Taylor data by an expansion in “mode” variables.
So the preprint’s own sharper bounds escape the hypotheses below, and in particular the conditions (H2) and (H3) of § 9. Our results apply to the clause-product route: on every formula after reduction to bounded occurrence, which is how the preprint obtains at bounded density and its weaker general bound in Section 2.8.
Cost model
We charge each point at least
and, for the preprint’s product-type evaluation, additionally . A scheme runs in time at most in this model if . All our lower bounds hold in this model; they are statements about running time only to the extent that the model’s charges are paid.
For the preprint’s evaluation they are. It enumerates each group’s assignments (), every tuple of measurement readings ( rows ), and computes restricted sums. Every edge of has a measured endpoint: by the definition of , an edge joins or a group with to such a group, and (3) makes such an measured. So the measured groups form a vertex cover, and since treewidth is at most the vertex-cover number [11], ; the product-type model implies the DP-type one.
The DP-type model is meant for an evaluation that still counts inside each group by enumeration, as the preprint does, but sums over measurement readings by dynamic programming instead of enumerating all tuples. The charge is justified for variable elimination over readings. Let be the measured groups and the torso: with the neighbourhood of every unmeasured group made a clique. Unmeasured groups are pairwise non-adjacent, and each one’s contribution depends jointly on the readings of its neighbours, so the readings interact along . A tree decomposition of extends to by attaching a bag for each unmeasured , so . Any elimination order over the readings creates a table indexed by at least readings, and a nonzero measurement row takes at least two values on Boolean inputs, so it costs at least . An evaluator that also counted inside groups by dynamic programming would not pay , and our model does not cover it.
The vanishing-product lemma
For let , the occurrences that lose their own variable at .
Lemma 6.1. Let with and . If is unmeasured then . If then is measured and adjacent to in .
Proof. If , (4) forces , in particular . If then , so and lies in the clique of .
Lemma 6.2 (Vanishing product). There is a point with .
Proof. Let . Then and . At every , vanishes to order at least . If for all , all Hermite data of are zero, so returns the same value on as on the zero polynomial, namely ; but it must return . Contradiction.
Remark 6.3. The proof uses only , and the exactness of up to degree . It applies verbatim to multi-parameter deformations with any recovery set that determines for polynomials of total degree at most . It fails as soon as the exactness degree falls below , which is what happens in the parity form (§ 5.1).
Necessary conditions for polynomial cost
Theorem 7.1 (Structure at a point). Let be the point of Lemma 6.2. Then
(i) ;
(ii) deleting at most edges of leaves every component inside one group (with the clauses assigned to it).
Proof. (i) Let be with removed from clause for every . If share a clause of , their groups are equal to or adjacent to it by Lemma 6.1, and lie in the clique of , so they are equal or adjacent in . Hence is a subgraph of the blow-up of in which each group is replaced by its variables, and replacing each group by its variables in every bag of a tree decomposition of gives . Every edge of missing from is incident to a variable with for some . There are at most such variables, and adding all of them to every bag gives a tree decomposition of of width at most .
(ii) Delete every occurrence with . By Lemma 6.1 each lies in or has in a measured group; there are at most of the first kind and at most of the second. Afterwards each clause is joined only to variables of its own group.
Theorem 7.2 (Necessary conditions). Suppose a scheme runs on in time at most in the cost model of § 5, with large.
(a) (DP-type) .
(b) (Product-type) Deleting at most edges of leaves components of at most variables. In particular, if is bounded, every connected component of has variables.
Proof. At the point of Lemma 6.2, give . Put . Then , which is at least if and at least otherwise. So forces , hence for large and . Theorem 7.1(i) gives (a). For (b), , and Theorem 7.1(ii) deletes at most edges. Deleting edges from a connected graph leaves at most components.
Exact counting runs in time by dynamic programming over a tree decomposition [26, 46], which is polynomial for treewidth . So a scheme of this kind cannot be polynomial on any family of treewidth . Between and , where treewidth dynamic programming is not polynomial, our bounds leave open whether such a scheme can be.
Corollary 7.3 (Paths). Let , which is countable in linear time. In the cost model, every product-type scheme on costs at least .
Proof. is a path, so leaving components of at most variables needs at least deletions, and . At the point of Lemma 6.2, . If the Taylor factor is at least and, with , the cost is at least . Otherwise and .
The preprint’s per-point evaluation is therefore super-polynomial even where counting is trivial; its gain over comes from balancing the three costs, not from exploiting structure.
Barriers on expanding formulas
Theorem 8.1 (Treewidth barrier). In the cost model, every DP-type (hence every product-type) scheme on costs at least
Proof. Write . At the point of Lemma 6.2, . If , the Taylor factor is at least . Otherwise , so .
Lemma 8.2. Let be a uniformly random 3-CNF with variables and clauses, . With high probability for a constant .
Proof. Two facts hold with high probability (proofs in Appendix § 13). (1) Every set of between and variables shares a clause with its complement in at least clauses. (2) Every set of variables occurs in at most clauses. A graph of treewidth has a separator with whose removal leaves components of at most vertices. If , take to be the largest component if it has at least vertices, and otherwise a union of components grown one at a time until it reaches ; in both cases . No clause meets two components, so every clause meeting both and its complement contains a variable of . By (1) and (2), , which forces .
Theorem 8.3 (Random 3-CNF). Let be uniformly random with clauses, . With high probability the clause-product scheme costs on in the cost model:
(a) applied to the preprint’s bounded-occurrence formula (variable copies on Tovey cycles),
and
(b) applied to the leaves of the preprint’s counting-preserving sparsification (its Appendix A, which uses the branching rule of [16 Fig. 5.1]), since the total cost is at least that of any single leaf.
Proof. (a) Contracting each Tovey cycle of to a vertex turns into a graph containing , so is a minor of and by Lemma 8.2. has variables; apply Theorem 8.1. (b) The preprint’s rule A.1 fixes an integer and thresholds . It branches on a nonempty proper subset of a width- clause when lies in at least width- clauses, choosing the smallest and then the largest . Its first child is , where is the set of the other clauses, so the clauses containing are replaced by the single clause ; there is no unit propagation. The parameter search sets , so once . Follow first children only. W.h.p. no pair of literals lies in three clauses, so no pair reaches , and the first sets that fire are single literals whose current degree is at least . Each adds the unit and removes the clauses containing . No 2-clauses are created, and units have no nonempty proper subsets, so every clause removed on this path contains a literal of degree at least in (a current degree never exceeds the original one). The leaf therefore contains every clause of without such a literal, plus unit clauses. W.h.p. the clauses with such a literal number at most with as , and grows as . Removing a clause removes at most three primal edges, and removing an edge lowers treewidth by at most one, so the leaf’s primal treewidth is at least , and (a) applies to it.
The gap, and what an improved scheme must change
The gap. On expanding inputs of bounded density, the clause-product scheme is confined between (Theorem 8.3) and the preprint’s , in the cost model. Our lower-bound technique cannot exceed : its only constraint is , which satisfies. Narrowing the gap needs one of two new ingredients. From above, a design on an expander with groups, interaction width, Taylor order and or polylogarithmically many rows per measured group would bring the scheme to . From below, one must show that measurements cannot absorb the cut. A measured group of dimension one can absorb two foreign occurrences with at only if the minor vanishes; that polynomial equals at , so each such pair is absorbed at no more than points. (Occurrences of the same variable can be absorbed together at no cost.) Turning this into a bound for groups with several measurement rows is open.
What must change. Besides the degree bound of Definition 5.1(a), which ties the number of occurrences to the degree up to which recovery is exact, Theorems 7.1–8.3 use three properties. A scheme that is polynomial in the cost model on random 3-CNF, or on any family of treewidth , must violate the degree bound or at least one of them. The preprint’s own sharper routes already do (§ 5.1): the parity form breaks the degree bound, and the tensor contraction violates (H2) and (H3). These are therefore necessary conditions for polynomial cost within the clause-product route, not barriers to faster algorithms in general.
(H1) Polynomial restoration at a point. Each occurrence’s dependence on its own variable is a polynomial in the deformation parameters, equal to 1 at the restoration point.
(H2) Generic-degree recovery. is recovered by a rule exact for all polynomials up to the a priori degree bound, not only for those of the special form (3).
(H3) Decomposition-priced evaluation. Evaluating one point costs at least exponentially in the group size, in the width of the group interaction, and in the Taylor order.
One natural way to make Taylor data cheap is excluded: if the design (4) held for all near , it would hold identically in and hence at , forcing for every foreign variable, that is, measuring the cut variables one by one. So the design cannot be extended to a neighbourhood of . Cheap Taylor data obtained in other ways, such as the mode expansion of the preprint’s Appendix D, is not excluded. Expansion is not an obstacle to every method; Gaussian elimination solves Tseitin formulas on expanders. The known algorithms that beat expansion exploit algebraic structure in the constraints, such as linearity over a field; the CSP dichotomy theorem [15, 56] says that 3-SAT has no polymorphism of the kind that makes such algorithms run in polynomial time, though it says nothing about subexponential time.
Experiments
All experiments use the code in Appendix C (Python with numpy) on a desktop machine. They are small by design: the claims are theorems, and the experiments check the code and the identity on which the scheme rests, evaluate the bounds and constants numerically, and relate them to a standard benchmark.
E0 and E5: the constants. E0 computes Table 1 and the crossover of Proposition B.2 by bisection. E5 evaluates the constants of Proposition 4.1: bits per edge at the root, and 18,534.8 if every level of the recursion shrinks by exactly the guaranteed factor . For 3-CNF at density 4.26 (about 45 network edges per variable) the certified exponent is at least bits, and about over all levels. It also counts the mode tuples of (D.14) exactly by a generating-function recurrence, for variables of each weight and budget : for , and the natural logarithm of the count is 0.866, 0.871 and 0.901 of the estimate used in the proposition.
E1: the interpolation identity, by brute force. This is a sanity check of the code and of the algebraic identity, not evidence for our theorems. For 30 random 3-CNF formulas with 4–7 variables and 2–4 clauses, random integer deformations of degree , and evaluation points, we computed exactly by summing (3) over all assignments and recovered by Lagrange interpolation. In 30 of 30 cases equals the brute-force count , while the clause polynomials took non-Boolean values at almost every point (for example, 12,039 non-Boolean clause values over the 25 points of one 7-variable instance).
E2: the bound on paths. We minimised the lower bound of Corollary 7.3, the necessary cost of a product-type scheme, exactly over integer parameters.
| minimal cost | ||
| 4.0 | 4.6 | |
| 8.0 | 10.0 | |
| 18.0 | 21.5 | |
| 37.0 | 46.4 | |
| 80.0 | 100.0 |
caption:
:::
The fitted exponent of is 0.327, against 1/3 in Corollary 7.3; the path itself is counted in linear time by a transfer matrix.
E3: treewidth on the SATLIB benchmark. For the first ten instances of each SATLIB uniform random 3-SAT family [33] we computed a rigorous lower bound on the primal treewidth (minor-min-width [28, 13]), an upper bound (min-fill elimination [12]), and the lower bound of Theorem 8.1 on the cost, minimised exactly over integer parameters, both at the treewidth lower bound and, for illustration, at the min-fill width.
| family | tw (MMW) | tw (min-fill) | bound (bits) | at min-fill width | |
| uf20-91 | 20 | 12.9 | 14.8 | 4.0 | 4.0 |
| uf50-218 | 50 | 19.4 | 33.8 | 4.4 | 6.0 |
| uf75-325 | 75 | 23.0 | 50.8 | 5.0 | 7.0 |
| uf100-430 | 100 | 27.0 | 67.8 | 5.0 | 8.0 |
| uf125-538 | 125 | 29.8 | 85.3 | 5.6 | 9.0 |
| uf150-645 | 150 | 32.4 | 102.8 | 6.0 | 10.0 |
| uf175-753 | 175 | 34.9 | 119.4 | 6.0 | 11.0 |
| uf200-860 | 200 | 37.1 | 135.3 | 6.0 | 11.8 |
| uf225-960 | 225 | 38.9 | 153.9 | 6.0 | 12.0 |
| uf250-1065 | 250 | 40.7 | 170.9 | 6.0 | 13.0 |
Table 1 (PDF p. 15).
The min-fill widths grow linearly, about , which is consistent with Lemma 8.2; they are upper bounds, so they do not confirm it. The heuristic lower bounds grow much more slowly, and at these sizes the rigorous barrier is only a few bits. The asymptotic content is the scaling: at the min-fill width the bound grows from 4 to 13 bits as goes from 20 to 250. At these sizes the preprint’s own algorithm would use direct summation (§ 4).
E4: exact counts against a standard method. Variable elimination along a min-fill order agreed with brute force on all 100 SATLIB uf20-91 instances (in our run, a mean of 0.004 s against 0.78 s; timings depend on the machine) and on 40 random 3-CNF formulas with at density 4.26, satisfiable or not. On uf50-218 the min-fill width is already 33–36: elimination along that order needs tables of at least entries, and brute force needs assignments. This does not make the instances hard to count: exact counters with component caching [49, 40] handle instances of this size routinely. The point is only that the treewidth that Theorem 8.1 charges the scheme is the same quantity that limits treewidth dynamic programming.
Methodology and use of AI tools
Pre-existing work. This note grew out of the authors’ earlier, unpublished work on degree-capped algebraic closures for systems of quadratic equations over , that is, polynomial-calculus refutations of bounded degree over extended systems. That work concerns proof systems, not the algorithms studied here, and none of its results is used in this note. Its starting points are standard: the correspondence between Cook’s theory and extended resolution [20], and expansion as the source of degree lower bounds for random CNF [6, 2]. It shaped the approach: the vanishing-product lemma is the analogue for interpolation of the observation that a degree-capped closure cannot cut an expander.
Use of AI. The analysis was carried out in the days following the preprint’s appearance with the help of Claude Opus 5.5 (Anthropic), used through Claude Code, to make a timelier analysis possible: reading the preprint and the literature, deriving and checking the arguments, extracting the constants of the preprint’s Appendix D, writing and running the verification code, and drafting the text. A separate instance with no access to the authors’ working notes refereed a draft against the preprint; its report led to the restriction of our limits to the clause-product route, to the cost-model qualifications, and to the extraction of the constants. The authors directed the work and take responsibility for all statements. Literature claims were checked against the sources cited; the novelty assessment rests on searches, not a systematic survey, and we welcome corrections.
Conclusion
The preprint’s general bound, , is subexponential as ; by itself it says nothing about any fixed , because the preprint states no constants. With a hidden constant of 3 it beats brute force only beyond , and with 10 only beyond (Table 1). Extracting the constants from its tensor-contraction proof, the running time it certifies for inputs of bounded density stays above unless , and on random 3-CNF at the satisfiability threshold unless (Proposition 4.1). The proof thus certifies no speed-up over brute force for any input of bounded density that could ever be written down; for denser inputs the constant depends on quantities the preprint leaves implicit. If the proof is correct, its significance is for the theory of exponential time: it refutes ETH, but it guarantees a faster count of no formula of bounded density and feasible size.
For the clause-product form of the interpolation algorithm, a one-line algebraic fact, that a product of polynomials equal to 1 at the origin cannot vanish to high order everywhere, shows that the balance of its three costs has a floor set by treewidth. In a cost model that charges what the preprint’s evaluation pays, the scheme cannot be polynomial beyond treewidth , costs on random 3-CNF, and in the preprint’s form is super-polynomial even on paths. The gap between and on expanders remains open. The preprint’s parity form and tensor contraction escape these limits, because they break the link between occurrences and the degree of exact recovery, or recover only modulo a power of two; whether similar limits hold for them is the natural next question.
Two properties of random 3-CNF
Let have variables and clauses, each on three distinct uniformly random variables with random signs.
Lemma A.1. If , then w.h.p. every set of variables with shares at least clauses with its complement.
Proof. For a random clause lies inside or inside its complement with probability at most , so the number of crossing clauses dominates , which falls below with probability at most . A union bound over at most sets gives . □
Lemma A.2. W.h.p., for every , every set of variables occurs in at most clauses.
Proof. For a fixed -set , the number of variables of in one clause is hypergeometric (three draws without replacement), so its moment generating function is at most that of ([31], Theorem 4). The clauses are independent, so the number of occurrences satisfies the Chernoff bound of , whose mean is : it exceeds with probability at most . Take with : this is at most , and a union bound over sets gives , which sums to over . □
The constants
Proof of Proposition 4.1
We use the notation of Appendix D of [44]. For an input with the algorithm builds the clause network of its Section D.2 and applies Theorem D.1 with . Each clause port is joined to the equality structure of its variable, which for a variable with ports has , or edges when , or ; each is at least . Every edge is then subdivided once. So , and for a 3-CNF in which every variable occurs at least three times.
Write and , so the root call retains valuation levels ((D.4)). If , that is , the root cannot be an active call, since Lemma D.5 needs ; the preprint then uses direct summation, which costs at least . If , where is the leaf threshold of (D.4), the root is a leaf and direct summation over its edges costs at least . These are the cases of the proposition in which the root is not active.
Otherwise the root is active. Fix an interpolation node with , write , , and . By Lemma D.5, with , so . The proof bounds the number of tuples satisfying (D.14) by
with the number of mode variables of each weight from (D.13), and then uses . For every the resulting estimate satisfies
by the inequality of arithmetic and geometric means, and . Each tuple produces child contractions, so the certified number of calls is at least this exponential, and every leaf is charged with . Converting to base two, the certified running time is at least with .
For the consequences, , which is at least unless . For a 3-CNF with and every variable occurring at least three times, the exponent is ; at the coefficient is 725,416, so the bound is below only if . Since , this is in the form .
Remark B.1. The argument keeps only the root, the dominant term of and the leaf charge, so it understates the certified bound. The preprint’s choice gives the factor in place of , about 1.7 times larger, and the deeper levels add about 15% (experiment E5). The parameter inequality of (D.5), on which the precision estimate (D.11) rests, requires at the root, that is .
The interpolation exponent with constant one
The interpolation algorithm runs in time up to polynomial factors. We ask when , taking the bound literally with constant one, first with the preprint’s natural logarithms and then with base-2 logarithms.
Proposition B.2. (i) satisfies if and only if , where and are the solutions of . Numerically, for every integer , since and .
(ii) With base-2 logarithms, satisfies if and only if or , where and is the smaller solution of . Moreover .
Proof. (i) For put , so that , an increasing function of . Then
with . Since , decreases on and increases on , with , and : there are exactly two zeros, and , and exactly between them. Bisection gives and , so and . For we have and , so ; these do not affect the integer range stated.
(ii) The same argument with gives with . Here , so decreases on and increases after, with , and . So its zeros are and , and exactly when or . At both sides of equal 256. Bisection gives .
The number has decimal digits. Neither crossover says anything about running times: the preprint does not state the constant, and with constant the crossovers move out as in Table 1.
Code
The script below reproduces all experiments; its output is listed after it. It requires Python 3 and numpy, and the SATLIB uniform random 3-SAT families unpacked in one directory.
"""Experiments for "Limits of the deformation-interpolation framework for counting satisfying assignments".
python3 limits_experiments.py <satlib-dir> [--quick]
E0 Where C n lnln n / sqrt(ln n), C n / sqrt(ln n) and n (lnln n)^2 / sqrt(ln n) cross n (Appendix B).
E1 Interpolation identity, brute force: H(0) = #F recovered from values of H at nonzero points.
E2 Product-evaluation bound on path formulas (the paths corollary): minimal cost exponent as n grows.
E3 SATLIB uniform random 3-SAT (uf20 ... uf250): treewidth bounds of the primal graph and the
framework cost bound they imply (the treewidth barrier).
E4 Exact model counts on SATLIB uf20/uf50 and random 3-CNF: brute force against variable
elimination along a min-fill order.
E5 The constants of the preprint’s Appendix D: the bound its proof certifies, where that bound
crosses 2^n, and an exact count of the mode tuples it enumerates.
Only numpy is required. <satlib-dir> holds the unpacked SATLIB families (uf20-91/, ...).
"""
import glob
import itertools
import math
import os
import random
import sys
import time
from fractions import Fraction
import numpy as np
# ---------------------------------------------------------------- formulas
def parse_dimacs(path):
"""Clauses as lists of signed 1-based literals. SATLIB files end with '%' and '0'."""
n, clauses, cur = 0, [], []
for line in open(path):
line = line.strip()
if not line or line[0] == 'c':
continue
if line[0] == '%':
break
if line[0] == 'p':
n = int(line.split()[2])
continue
for tok in line.split():
lit = int(tok)
if lit == 0:
if cur:
clauses.append(cur)
cur = []
else:
cur.append(lit)
return n, clauses
def random_3cnf(n, m, rng):
out = []
for _ in range(m):
vs = rng.sample(range(1, n + 1), 3)
out.append([v if rng.random() < .5 else -v for v in vs])
return out
# ---------------------------------------------------------------- counting
def brute_count(n, clauses):
"""Exact count over all 2^n assignments, vectorised (n <= 24)."""
x = np.arange(1 << n, dtype=np.uint32)
ok = np.ones(1 << n, dtype=bool)
for cl in clauses:
sat = np.zeros(1 << n, dtype=bool)
for lit in cl:
bit = ((x >> (abs(lit) - 1)) & 1).astype(bool)
sat |= bit if lit > 0 else ~bit
ok &= sat
return int(ok.sum())
def primal_graph(n, clauses):
adj = {v: set() for v in range(1, n + 1)}
for cl in clauses:
vs = {abs(l) for l in cl}
for a in vs:
adj[a] |= vs - {a}
return adj
def min_fill_order(adj):
"""Elimination order by minimum fill-in (ties: minimum degree). Returns (order, width)."""
g = {v: set(nb) for v, nb in adj.items()}
order, width = [], 0
while g:
best, best_key = None, None
for v, nb in g.items():
nbl = list(nb)
fill = sum(1 for i in range(len(nbl)) for j in range(i + 1, len(nbl)) if nbl[j] not in g[nbl[i]])
key = (fill, len(nb))
if best_key is None or key < best_key:
best, best_key = v, key
nb = g.pop(best)
width = max(width, len(nb))
for a in nb:
g[a] |= nb - {a}
g[a].discard(best)
order.append(best)
return order, width
def mmw_lower_bound(adj):
"""Minor-min-width: contract a minimum-degree vertex into its minimum-degree neighbour.
Treewidth is minor-monotone and at least the minimum degree, so the maximum minimum
degree seen is a lower bound on treewidth."""
g = {v: set(nb) for v, nb in adj.items()}
lb = 0
while len(g) > 1:
v = min(g, key=lambda u: len(g[u]))
lb = max(lb, len(g[v]))
if not g[v]:
del g[v]
continue
u = min(g[v], key=lambda w: len(g[w]))
for w in g[v]:
if w != u:
g[w].discard(v)
g[w].add(u)
g[u].add(w)
g[u].discard(v)
del g[v]
return lb
def elimination_count(n, clauses, order):
"""Exact count by variable elimination: clause indicator factors, multiplied and summed out
along ‘order‘. Factor = (sorted variable tuple, int64 table with one axis per variable)."""
factors, used = [], set()
for cl in clauses:
vs = sorted({abs(l) for l in cl})
used |= set(vs)
t = np.zeros((2,) * len(vs), dtype=np.int64)
for a in itertools.product((0, 1), repeat=len(vs)):
val = dict(zip(vs, a))
t[a] = any((val[abs(l)] == 1) == (l > 0) for l in cl)
factors.append((tuple(vs), t))
def mul(f, g):
u = tuple(sorted(set(f[0]) | set(g[0])))
def lift(h):
return h[1].reshape([2 if x in h[0] else 1 for x in u])
return u, lift(f) * lift(g)
for v in order:
bucket = [f for f in factors if v in f[0]]
if not bucket:
continue
factors = [f for f in factors if v not in f[0]]
prod = bucket[0]
for f in bucket[1:]:
prod = mul(prod, f)
ax = prod[0].index(v)
factors.append((prod[0][:ax] + prod[0][ax + 1:], prod[1].sum(axis=ax)))
total = 1
for f in factors:
total *= int(f[1])
return total * (1 << (n - len(used)))
# ------------------------------------------------------------ E1: the interpolation identity
def clause_poly(cl, inputs):
"""phi_e = 1 - prod over literals of (1 - L), L = input (positive) or 1 - input (negative)."""
p = 1
for lit, z in zip(cl, inputs):
L = z if lit > 0 else 1 - z
p *= (1 - L)
return 1 - p
def H_value(n, clauses, forms, t):
"""H(t) = sum over Boolean x of prod_e phi_e(<P_{e,v}(t), x>), exactly (integers)."""
total, nonboolean = 0, 0
for x in itertools.product((0, 1), repeat=n):
prod = 1
for ci, cl in enumerate(clauses):
ins = []
for j, lit in enumerate(cl):
coeffs = forms[(ci, j)] # list over powers of T of vectors
val = sum(sum(c[i] * x[i] for i in range(n)) * t ** k for k, c in enumerate(coeffs))
ins.append(val)
ph = clause_poly(cl, ins)
nonboolean += ph not in (0, 1)
prod *= ph
total += prod
return total, nonboolean
def lagrange_at_zero(points, values):
acc = Fraction(0)
for i, (ti, vi) in enumerate(zip(points, values)):
w = Fraction(1)
for j, tj in enumerate(points):
if j != i:
w *= Fraction(0 - tj, ti - tj)
acc += w * vi
return acc
def experiment_interpolation(trials, rng):
print('E1 interpolation identity (brute force)')
ok = 0
for trial in range(trials):
n = rng.randint(4, 7); m = rng.randint(2, 4); R = rng.choice([1, 2])
clauses = random_3cnf(n, m, rng)
forms = {}
for ci, cl in enumerate(clauses):
for j, lit in enumerate(cl):
v = abs(lit) - 1
base = [1 if i == v else 0 for i in range(n)]
forms[(ci, j)] = [base] + [[rng.randint(-2, 2) for _ in range(n)] for _ in range(R)]
d = 3 * m * R
pts = list(range(1, d + 2))
vals, nb = [], 0
for t in pts:
h, b = H_value(n, clauses, forms, t)
vals.append(h); nb += b
rec = lagrange_at_zero(pts, vals)
truth = brute_count(n, [[l for l in cl] for cl in clauses])
ok += rec == truth
if trial < 3:
print(f' n={n} m={m} R={R} deg<= {d}: recovered H(0)={rec} brute force #F={truth}; '
f'non-Boolean clause values at the {len(pts)} points: {nb}')
print(f' {ok}/{trials} instances: H(0) recovered exactly equals #F')
# ---------------------------------------------------------------- E2/E3: the bounds
def log2_binom(n, q):
return (math.lgamma(n + 1) - math.lgamma(q + 1) - math.lgamma(n - q + 1)) / math.log(2)
def log2_taylor_cost(n, q):
"""The Taylor data of order q cost sum_{j<=q} 2^j C(n, j) >= C(n, min(q, n//2))."""
return log2_binom(n, min(q, n // 2))
def treewidth_bound_bits(n, tw):
"""Treewidth barrier: some point has (w+1)s - 1 + q >= tw; cost >= 2^s, 2^w, C(n,q).
Minimal max(s, w, log2 C(n, min(q, n/2))) over integers s >= 1, w >= 0, q >= 0."""
best = float('inf')
for s in range(1, tw + 2):
for w in range(0, tw + 1):
q = max(0, tw + 1 - (w + 1) * s)
250 if q > n:
251 continue
252 best = min(best, max(s, w, log2_taylor_cost(n, q)))
253 return best
254
255
256 def path_bound_bits(n, b=2):
257 """Paths corollary: some point deletes <= q + b*rho*s edges and leaves
258 components of <= s variables, so q + b*rho*s >= ceil(n/s) - 1. Minimal max(s, rho, log2 C(n, min(q, n/2)))
259 """
260 best = float('inf')
261 for s in range(1, n + 1):
262 need = math.ceil(n / s) - 1
263 if s >= best:
264 break
265 for rho in range(0, need // (b * s) + 2):
266 q = max(0, need - b * rho * s)
267 if q > n:
268 continue
269 best = min(best, max(s, rho, log2_taylor_cost(n, q)))
270 if q == 0:
271 break
272 return best
273
274 def experiment_paths():
275 print('E2 product-evaluation bound on path formulas (bits, i.e. log2 of the minimal cost)')
276 xs, ys = [], []
277 for n in (10 ** 2, 10 ** 3, 10 ** 4, 10 ** 5, 10 ** 6):
278 bits = path_bound_bits(n)
279 xs.append(math.log(n)); ys.append(math.log(bits))
280 print(f' n={n:>8} bound={bits:8.1f} bits n^(1/3)={n ** (1 / 3):8.1f}')
281 k = len(xs); mx, my = sum(xs) / k, sum(ys) / k
282 slope = sum((a - mx) * (b - my) for a, b in zip(xs, ys)) / sum((a - mx) ** 2 for a in xs)
283 print(f' fitted exponent of n: {slope:.3f} (paths corollary: 1/3 up to logarithms)')
284
285
286 def experiment_satlib(root, per_family):
287 print('E3 SATLIB uniform random 3-SAT: primal treewidth bounds and the implied framework bound')
288 print(f' {"family":>11} {"n":>4} {"tw >= (MMW)":>12} {"tw <= (min-fill)":>17} {"bound bits":>11} {"at min-fill":>12} {"sec":>6}')
289 for fam in sorted(glob.glob(os.path.join(root, 'uf*')), key=lambda p: int(os.path.basename(p)[2:].split('-')[0])):
290 if not os.path.isdir(fam):
291 continue
292 files = sorted(glob.glob(os.path.join(fam, '**', '*.cnf'), recursive=True))[:per_family]
293 if not files:
294 continue
295 lbs, ubs, bits, bits_ub = [], [], [], []
296 t0 = time.time()
297 for f in files:
298 n, cl = parse_dimacs(f)
299 adj = primal_graph(n, cl)
300 lb = mmw_lower_bound(adj)
301 _, ub = min_fill_order(adj)
302 lbs.append(lb); ubs.append(ub); bits.append(treewidth_bound_bits(n, lb))
303 bits_ub.append(treewidth_bound_bits(n, ub)) # what the bound would give if tw equalled the min-fill width
304 k = len(files)
305 print(f' {os.path.basename(fam):>11} {n:>4} {sum(lbs) / k:>12.1f} {sum(ubs) / k:>17.1f} '
306 f'{sum(bits) / k:>11.2f} {sum(bits_ub) / k:>12.2f} {(time.time() - t0) / k:>6.2f}')
307
308
309 def experiment_counting(root, rng, n_uf20, n_uf50):
310 print('E4 exact counts: brute force against variable elimination (min-fill order)')
311 agree = total = 0
312 files = sorted(glob.glob(os.path.join(root, 'uf20-91', '**', '*.cnf'), recursive=True))[:n_uf20]
313 t_bf = t_ve = 0.0
314 for f in files:
315 n, cl = parse_dimacs(f)
316 t0 = time.time(); a = brute_count(n, cl); t_bf += time.time() - t0
317 t0 = time.time(); order, _ = min_fill_order(primal_graph(n, cl)); b = elimination_count(n, cl, order);
t_ve += time.time() - t0
318 agree += a == b; total += 1
319 print(f' SATLIB uf20-91: {agree}/{total} agree; mean time brute force {t_bf / max(total, 1):.3f}s, '
320 f'elimination {t_ve / max(total, 1):.3f}s')
321 agree = total = 0
322 for _ in range(40):
323 n = 20; cl = random_3cnf(n, round(4.26 * n), rng)
324 order, _ = min_fill_order(primal_graph(n, cl))
325 agree += brute_count(n, cl) == elimination_count(n, cl, order); total += 1
326 print(f' random 3-CNF n=20 ratio 4.26 (satisfiable and not): {agree}/{total} agree')
327 files = sorted(glob.glob(os.path.join(root, 'uf50-218', '**', '*.cnf'), recursive=True))[:n_uf50]
328 counts, widths, t_ve = [], [], 0.0
329 for f in files:
330 n, cl = parse_dimacs(f)
331 order, w = min_fill_order(primal_graph(n, cl))
332 widths.append(w)
333 if w > 22: # tables of 2^(w+1) entries; beyond this the elimination does not fit in memory
334 continue
335 t0 = time.time(); counts.append(elimination_count(n, cl, order)); t_ve += time.time() - t0
336 print(f' SATLIB uf50-218: min-fill width {min(widths)}..{max(widths)} over {len(widths)} instances; '
337 f'{len(counts)} within width 22 counted by elimination'
338 + (f', counts {min(counts)}..{max(counts)}' if counts else '; none fits, 2^50 is beyond brute force')
339 )
340
341
342 def bisect_root(f, lo, hi, iters=100):
343 """A zero of f in [lo, hi], given f(lo) and f(hi) of opposite signs."""
344 flo = f(lo)
345 for _ in range(iters):
346 mid = (lo + hi) / 2
347 if (f(mid) > 0) == (flo > 0):
348 lo, flo = mid, f(mid)
349 else:
350 hi = mid
351 return (lo + hi) / 2
352
353
354 def last_crossing_u(C):
355 """Largest u = ln n with sqrt(u) = C ln u, so that C n lnln n / sqrt(ln n) < n for all larger n.
356 None when sqrt(u) > C ln u for every u > 1."""
357 g = lambda u: math.sqrt(u) - C * math.log(u)
358 umin = (2 * C) ** 2 # g is smallest here: g’(u) = 1/(2 sqrt u) - C/u
359 if g(umin) > 0:
360 return None
361 hi = umin
362 while g(hi) <= 0:
363 hi *= 2
364 return bisect_root(g, umin, hi)
365
366
367 def experiment_crossover():
368 """Theorem 1.1 with a hidden constant C, in the preprint’s natural logarithms: the general
369 exponent C n lnln n / sqrt(ln n) and the bounded-density exponent C n / sqrt(ln n) against n.
370 Then the interpolation exponent rho(n) = n (ln ln n)^2 / sqrt(ln n) can cross at one constant one:
371 rho(n) < n iff u - 4 ln u > 0, u = ln ln n (and a - 4 log2 a > 0, a = log2 log2 n, in base 2)."""
372 print('EO where the preprint’s exponents cross n')
373 print(f' {"C":>4} {"general: n beyond":>22} {"bounded density: n beyond":>26}')
374 for C in (1, 2, 3, 5, 10, 20, 50):
375 u = last_crossing_u(C)
376 gen = 'every n > e' if u is None else f'10^{u / math.log(10):.1f}'
377 print(f' {C:>4} {gen:>22} {"10^%.1f" % (C * C / math.log(10)):>26}')
378 g = lambda u: u - 4 * math.log(u)
379 u1, u2 = bisect_root(g, 1.0, 4.0), bisect_root(g, 4.0, 20.0)
380 print(f' rho(n), natural logs: zeros of u - 4 ln u at u1 = {u1:.4f} (n = {math.exp(math.exp(u1)):.1f})
and ’
380 f’u2 = {u2:.4f} (n = 10^{math.exp(u2) / math.log(10):.1f})’)
381 f = lambda a: a - 4 * math.log2(a)
382 a1 = bisect_root(f, 1.0, 2.0)
383 print(f’ rho(n), base 2: zeros of a - 4 log2 a at a1 = {a1:.4f} (n1 = 2^2^a1 = {2 ** (2 ** a1):.2f}) ’
384 f’and a2 = 16 (f(16) = {f(16):.1f}); 2^65536 has {math.floor(65536 * math.log10(2)) + 1} digits’)
385
386
387 # ---------------------------------------------------------------- E5: the constants of Appendix D
388
389 EPS_LOG2 = 17 # epsilon = 1 / (128 * 1024) = 2^-17 in (D.4)
390 SHRINK = 3 / 32 # a child has at most 6M/r = 3M/32 edges (Section D.4.6)
391
392
393 def appendix_d_constants():
394 """Per-edge constants, in bits per edge per 1/sqrt(lambda), of the bound certified at the root
395 call (K0) and summed over levels whose edge counts shrink by exactly SHRINK (K_all).
396 Root call: (D.15) with the best theta gives 2 pi sqrt(M p_t / D) nats; (D.11) has
397 p_t >= 8 h D_t >= 24 M D_t / u with h = ceil(3M/u); u = floor(lambda / 2^17)."""
398 K0 = 2 * math.pi * math.sqrt(24 * 2 ** EPS_LOG2) / math.log(2)
399 ratio = SHRINK * math.sqrt(2) # M_d / sqrt(u_d) shrinks by this per level
400 return K0, K0 / (1 - ratio)
401
402
403 def network_edges_3cnf(alpha):
404 """Edges of the D.2 network per variable for a 3-CNF with m = alpha n clauses, every variable
405 occurring at least three times: clause ports 3m, an equality tree with 2d - 3 edges for a
406 variable with d ports, every edge subdivided once: 2 (6m - 3n)."""
407 return 12 * alpha - 6
408
409
410 def tuple_count(N, p):
411 """Exact number of tuples (beta_Z) over N variables of each weight w >= 1 with sum w beta < p:
412 sum of the coefficients of x^0 .. x^(p-1) in prod_w (1 - x^w)^(-N)."""
413 c = [1] + [0] * (p - 1)
414 for w in range(1, p):
415 for _ in range(N):
416 for i in range(w, p):
417 c[i] += c[i - w]
418 return sum(c)
419
420
421 def experiment_appendix_d():
422 print(’E5 the constants of the preprint\’s Appendix D’)
423 K0, Kall = appendix_d_constants()
424 print(f’ root call: at least 2^(K0 M0 / sqrt(lambda)) mode tuples, K0 = {K0:,.1f}; ’
425 f’all levels at the guaranteed shrink: K = {Kall:,.1f}’)
426 lam = (2 * K0) ** 2
427 print(f’ any input (M0 >= 2 per occurring variable): below 2^n only if lambda = log2(n+m) > {lam:.3e}’)
428 for alpha in (4.26, 10.0): # dense enough that almost every variable occurs >= 3 times
429 e = network_edges_3cnf(alpha)
430 for name, K in ((’root’, K0), (’all levels’, Kall)):
431 per_var = K * e + (1 + alpha) # (K M0 + s) / n, the leaf term H >= s / sqrt(lambda)
432 lam = per_var ** 2
433 print(f’ {alpha:5.2f}f {e:.2f} edges/variable, {name:>10}: exponent ’
434 f’{per_var:.0f} n / sqrt(log2 s) bits, below n only if log2 n > {lam - math.log2(1 + alpha)
435 :.2e}’)
436 f’as C n / sqrt(ln n): C = {per_var * math.sqrt(math.log(2)):.0f}’)
437 x = 5 * EPS_LOG2
438 print(f’ (D.5) lambda^(4/5) <= u at the root: lambda / 2^17 >= lambda^(4/5) iff log2 lambda >= {x} ’,
439 f’i.e. log2 s >= 2^{x}’)
440 print(’ mode tuples, exact count against exp(2 pi sqrt(p N / 6)):’)
441 for N, p in ((2, 200), (6, 300), (6, 600)):
442 cnt = tuple_count(N, p)
443 est = 2 * math.pi * math.sqrt(p * N / 6)
444 print(f’ N={N} p={p}: ln count = {math.log(cnt):7.2f}, estimate {est:7.2f}, ratio {math.log(cnt) /
est:.3f}’)
445
446 def main():
447 root = sys.argv[1] if len(sys.argv) > 1 else ’satlib’
448 quick = ’--quick’ in sys.argv
449 rng = random.Random(2026)
450 experiment_crossover()
451 experiment_interpolation(10 if quick else 30, rng)
452 experiment_paths()
453 experiment_satlib(root, 3 if quick else 10)
454 experiment_counting(root, rng, 20 if quick else 100, 5 if quick else 20)
455 experiment_appendix_d()
456
457
458 if __name__ == ’__main__’:
459 main()
Output
1 E0 where the preprint’s exponents cross n
2 C general: n beyond bounded density: n beyond
3 1 every n > e 10^0.4
4 2 10^32.2 10^1.7
5 3 10^125.5 10^3.9
6 5 10^555.7 10^10.9
7 10 10^3517.4 10^43.4
8 20 10^20035.2 10^173.7
9 50 10^181955.6 10^1085.7
10 rho(n), natural logs: zeros of u - 4 ln u at u1 = 1.4296 (n = 65.2) and u2 = 8.6132 (n = 10^2390.2)
11 rho(n), base 2: zeros of a - 4 log2 a at a1 = 1.2396 (n1 = 2^2^a1 = 5.14) and a2 = 16 (f(16) = 0.0); 2^65536
has 19729 digits
12 E1 interpolation identity (brute force)
13 n=4 m=3 R=1 deg<= 9: recovered H(0)=11 brute force #F=11; non-Boolean clause values at the 10 points: 294
14 n=7 m=4 R=2 deg<= 24: recovered H(0)=74 brute force #F=74; non-Boolean clause values at the 25 points: 12039
15 n=4 m=2 R=2 deg<= 12: recovered H(0)=12 brute force #F=12; non-Boolean clause values at the 13 points: 332
16 30/30 instances: H(0) recovered exactly equals #F
17 E2 product-evaluation bound on path formulas (bits, i.e. log2 of the minimal cost)
18 n= 100 bound= 4.0 bits n^(1/3)= 4.6
19 n= 1000 bound= 8.0 bits n^(1/3)= 10.0
20 n= 10000 bound= 18.0 bits n^(1/3)= 21.5
21 n= 100000 bound= 37.0 bits n^(1/3)= 46.4
22 n=1000000 bound= 80.0 bits n^(1/3)= 100.0
23 fitted exponent of n: 0.327 (paths corollary: 1/3 up to logarithms)
24 E3 SATLIB uniform random 3-SAT: primal treewidth bounds and the implied framework bound
25 family n tw >= (MMW) tw <= (min-fill) bound bits at min-fill sec
26 uf20-91 20 12.9 14.8 4.00 4.00 0.00
27 uf50-218 50 19.4 33.8 4.40 6.00 0.03
28 uf75-325 75 23.0 50.8 5.00 7.00 0.10
29 uf100-430 100 27.0 67.8 5.00 8.00 0.31
30 uf125-538 125 29.8 85.3 5.60 9.00 0.70
31 uf150-645 150 32.4 102.8 6.00 10.00 1.35
32 uf175-753 175 34.9 119.4 6.00 11.00 2.27
33 uf200-860 200 37.1 135.3 6.00 11.80 3.72
34 uf225-960 225 38.9 153.9 6.00 12.00 5.73
35 uf250-1065 250 40.7 170.9 6.00 13.00 7.90
36 E4 exact counts: brute force against variable elimination (min-fill order)
37 SATLIB uf20-91: 100/100 agree; mean time brute force 0.781s, elimination 0.004s
38 random 3-CNF n=20 ratio 4.26 (satisfiable and not): 40/40 agree
39 SATLIB uf50-218: min-fill width 33..36 over 20 instances; 0 within width 22 counted by elimination; none
fits, 2^50 is beyond brute force
40 E5 The constants of the preprint’s Appendix D
41 root call: at least 2^(K0 M0 / sqrt(lambda)) mode tuples, K0 = 16,077.4; all levels at the guaranteed shrink
: K = 18,534.8
42 any input (M0 >= 2 per occurring variable): below 2^n only if lambda = log2(n+m) > 1.034e+09
43 3-CNF density 4.26 (45.12 edges/variable), root: exponent 725,416 n / sqrt(log2 s) bits, below n only
if log2 n > 5.26e+11; as C n / sqrt(ln n): C = 603,949
44 3-CNF density 4.26 (45.12 edges/variable), all levels: exponent 836,293 n / sqrt(log2 s) bits, below n only
if log2 n > 6.99e+11; as C n / sqrt(ln n): C = 696,260
45 3-CNF density 10.00 (114.00 edges/variable), root: exponent 1,832,831 n / sqrt(log2 s) bits, below n
only if log2 n > 3.36e+12; as C n / sqrt(ln n): C = 1,525,932
46 3-CNF density 10.00 (114.00 edges/variable), all levels: exponent 2,112,973 n / sqrt(log2 s) bits, below n
only if log2 n > 4.46e+12; as C n / sqrt(ln n): C = 1,759,165
47 (D.5) lambda^(4/5) <= u at the root: lambda / 2^17 >= lambda^(4/5) iff log2 lambda >= 85, i.e. log2 s >=
2^85
48 mode tuples, exact count against exp(2 pi sqrt(p N / 6)):
49 N=2 p=200: ln count = 44.44, estimate 51.30, ratio 0.866
50 N=6 p=300: ln count = 94.76, estimate 108.83, ratio 0.871
51 N=6 p=600: ln count = 138.67, estimate 153.91, ratio 0.901References
- [1]A. Abboud, R. Williams, H. Yu. More applications of the polynomial method to algorithm design. SODA 2015.
- [2]M. Alekhnovich, A. Razborov. Lower bounds for polynomial calculus: non-binomial case. Proc. Steklov Inst. Math. 242, 2003.
- [3]J. Alman. Limits on the universal method for matrix multiplication. CCC 2019.arxiv.org/abs/1812.08731
- [4]J. Alman, V. Vassilevska Williams. Limits on all known (and some unknown) approaches to matrix multiplication. FOCS 2018.
- [5]A. Ambainis, Y. Filmus, F. Le Gall. Fast matrix multiplication: limitations of the Coppersmith–Winograd method. STOC 2015.
- [6]E. Ben-Sasson, R. Impagliazzo. Random CNF’s are hard for the polynomial calculus. Comput. Complexity 19, 2010.
- [7]E. Ben-Sasson, A. Wigderson. Short proofs are narrow—resolution made simple. J. ACM 48(2), 2001.
- [8]A. Björklund. Determinant sums for undirected Hamiltonicity. FOCS 2010.
- [9]A. Björklund, T. Husfeldt, M. Koivisto. Set partitioning via inclusion–exclusion. SIAM J. Comput. 39(2), 2009.DOI
- [10]A. Björklund, P. Kaski, R. Williams. Solving systems of polynomial equations over GF(2) by a parity-counting self-reduction. ICALP 2019.
- [11]H. L. Bodlaender. A tourist guide through treewidth. Acta Cybernetica 11, 1993.
- [12]H. L. Bodlaender, A. M. C. A. Koster. Treewidth computations I. Upper bounds. Inform. and Comput. 208(3), 2010.DOI
- [13]H. L. Bodlaender, A. M. C. A. Koster. Treewidth computations II. Lower bounds. Inform. and Comput. 209(7), 2011.
- [14]R.-D. Buhai, J.-T. Hsieh, A. Jain, P. K. Kothari. The quasi-polynomial low-degree conjecture is false. arXiv:2505.17360, 2025.arxiv.org/abs/2505.17360
- [15]A. A. Bulatov. A dichotomy theorem for nonuniform CSPs. FOCS 2017.arxiv.org/abs/1703.03021
- [16]C. Calabro. The exponential complexity of satisfiability problems. PhD thesis, UC San Diego, 2009.
- [17]C. Calabro, R. Impagliazzo, R. Paturi. A duality between clause width and clause density for SAT. CCC 2006.DOI
- [18]M. Christandl, P. Vrana, J. Zuiddam. Barriers for fast matrix multiplication from irreversibility. CCC 2019.
- [19]V. Chvátal, E. Szemerédi. Many hard examples for resolution. J. ACM 35(4), 1988.DOI
- [20]S. A. Cook. Feasibly constructive proofs and the propositional calculus. STOC 1975.DOI
- [21]J. M. Crawford, L. D. Auton. Experimental results on the crossover point in random 3-SAT. Artificial Intelligence 81, 1996.DOI
- [22]R. Curticapean. Block interpolation: a framework for tight exponential-time counting complexity. Inform. and Comput. 261, 2018.
- [23]V. Dahllöf, P. Jonsson, M. Wahlström. Counting models for 2SAT and 3SAT formulae. Theoret. Comput. Sci. 332, 2005.DOI
- [24]H. Dell, T. Husfeldt, D. Marx, N. Taslaman, M. Wahlén. Exponential time complexity of the permanent and the Tutte polynomial. ACM Trans. Algorithms 10(4), 2014.
- [25]I. Dinur. Improved algorithms for solving polynomial systems over GF(2) by multiple parity-counting. SODA 2021.arxiv.org/abs/2005.04800
- [26]E. Fischer, J. A. Makowsky, E. V. Ravve. Counting truth assignments of formulas of bounded tree-width or clique-width. Discrete Appl. Math. 156(4), 2008.DOI
- [27]Y. Gao. Treewidth of Erdős–Rényi random graphs, random intersection graphs, and scale-free random graphs. Discrete Appl. Math. 160, 2012.DOI
- [28]V. Gogate, R. Dechter. A complete anytime algorithm for treewidth. UAI 2004.arxiv.org/abs/1207.4109
- [29]T. D. Hansen, H. Kaplan, O. Zamir, U. Zwick. Faster k-SAT algorithms using biased-PPSZ. STOC 2019.DOI
- [30]T. Hertli. 3-SAT faster and simpler—unique-SAT bounds for PPSZ hold in general. SIAM J. Comput. 43(2), 2014.
- [31]W. Hoeffding. Probability inequalities for sums of bounded random variables. J. Amer. Statist. Assoc. 58(301), 1963.
- [32]J. Holmgren, A. S. Wein. Counterexamples to the low-degree conjecture. ITCS 2021.
- [33]H. H. Hoos, T. Stützle. SATLIB: an online resource for research on SAT. In SAT 2000, IOS Press, 2000.
- [34]S. B. Hopkins. Statistical inference and the sum of squares method. PhD thesis, Cornell University, 2018.DOI
- [35]R. Impagliazzo, R. Paturi. On the complexity of k-SAT. J. Comput. System Sci. 62(2), 2001.DOI
- [36]R. Impagliazzo, R. Paturi, F. Zane. Which problems have strongly exponential complexity? J. Comput. System Sci. 63(4), 2001.
- [37]I. Koutis. Faster algebraic algorithms for path and packing problems. ICALP 2008.DOI
- [38]K. Kutzkov. Complementary branching for #SAT: bounded-degree bounds and faster #3-SAT. IJCAI 2026.DOI
- [39]D. Kunisky, A. S. Wein, A. S. Bandeira. Notes on computational hardness of hypothesis testing: predictions using the low-degree likelihood ratio. arXiv:1907.11636, 2019.arxiv.org/abs/1907.11636
- [40]J.-M. Lagniez, P. Marquis. An improved decision-DNNF compiler. IJCAI 2017.DOI
- [41]C. Lee, J. Lee, S. Oum. Rank-width of random graphs. J. Graph Theory 70(3), 2012.
- [42]D. Lokshtanov, R. Paturi, S. Tamaki, R. Williams, H. Yu. Beating brute force for systems of polynomial equations over finite fields. SODA 2017.DOI
- [43]D. Mitchell, B. Selman, H. Levesque. Hard and easy distributions of SAT problems. AAAI 1992.
- [44]OpenAI. The exponential time hypothesis is false. Preprint, 17 October 2026, revised 25 October 2026.hub.valency.io/works/W_h8uqubsk
- [45]R. Paturi, P. Pudlák, M. E. Saks, F. Zane. An improved exponential-time algorithm for k-SAT. J. ACM 52(3), 2005.
- [46]M. Samer, S. Szeider. Algorithms for propositional model counting. J. Discrete Algorithms 8(1), 2010.
- [47]D. Scheder. PPSZ is better than you think. TheoretICCS 3, 2024.
- [48]U. Schöning. A probabilistic algorithm for k-SAT and constraint satisfaction problems. FOCS 1999.
- [49]M. Thurley. sharpSAT—counting models with advanced component caching and implicit BCP. SAT 2006.
- [50]C. A. Tovey. A simplified NP-complete satisfiability problem. Discrete Appl. Math. 8, 1984.DOI
- [51]L. G. Valiant. The complexity of computing the permanent. Theoret. Comput. Sci. 8, 1979.DOI
- [52]V. Vassilevska Williams. On some fine-grained questions in algorithms and complexity. Proc. ICM 2018.DOI
- [53]M. Wahlström. A tighter bound for counting max-weight solutions to 2SAT instances. IWPEC 2008.DOI
- [54]R. Williams. Finding paths of length k in O*(2^k) time. Inform. Process. Lett. 109(6), 2009.arxiv.org/abs/0807.3026
- [55]R. Williams. Faster all-pairs shortest paths via circuit complexity. STOC 2014.
- [56]D. Zhuk. A proof of the CSP dichotomy conjecture. J. ACM 67(5), 2020.