betaFeedback

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 kk-CNF formula in time 2Ok(nlog⁡log⁡n/log⁡n)2^{O_k(n\log\log n/\sqrt{\log n})}, and 2O(n/log⁡n)2^{O(n/\sqrt{\log n})} 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 n(log⁡log⁡n)2/log⁡nn(\log\log n)^2/\sqrt{\log n}. This note does four things. First, it explains the interpolation algorithm in plain terms. Second, it asks how large nn must be for the bounds to bite. The preprint states no constants, so we treat the hidden constant CC as a parameter: the general bound beats the 2n2^n of brute force only beyond n≈1032n\approx 10^{32} for C=2C=2, 1012610^{126} for C=3C=3 and 10351710^{3517} for C=10C=10. We then extract the constants from the tensor-contraction proof: for every input with mm clauses at bounded density, the running time it certifies stays above 2n2^n unless log⁡2(n+m)>109\log_2(n+m)>10^9, and on random 3-CNF at the satisfiability threshold unless log⁡2n>5×1011\log_2 n>5\times10^{11}. So the bounds are subexponential as n→∞n\to\infty, 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 O(log⁡3n)O(\log^3 n) variables with per-point evaluation, or primal treewidth O(log⁡2n)O(\log^2 n) with dynamic programming over the groups. So the scheme costs 2Ω(tw)2^{Ω(\sqrt{\mathrm{tw}})} at treewidth tw\mathrm{tw}, 2Ω(n)2^{Ω(\sqrt n)} with high probability on random 3-CNF above clause density 3, and 2Ω(n1/3)2^{Ω(n^{1/3})} 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 nn variables needs time 2δn2^{\delta n} for some δ>0\delta>0. 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 #kk-SAT can be solved deterministically in time (n+m)Ok(1)2Ok(nlog⁡log⁡n/log⁡n)(n+m)^{O_k(1)}2^{O_k(n\log\log n/\sqrt{\log n})} and polynomial space, and in time (n+m)Ok,D(1)2Ok,D(n/log⁡n)(n+m)^{O_{k,D}(1)}2^{O_{k,D}(n/\sqrt{\log n})} when m≤Dnm\le Dn. 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

ρ(n)=n(log⁡log⁡n)2log⁡n.(1)\rho(n)=\frac{n(\log\log n)^2}{\sqrt{\log n}}. \tag*{(1)}

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 kk-CNF the preprint derives only 2Ok(n(log⁡log⁡n)k+1/(log⁡n)1/(2k))2^{O_k(n(\log\log n)^{k+1}/(\log n)^{1/(2k)})} from it (its Section 2.8), but on formulas of bounded density, where variable copies alone give O(n)O(n) variables, it yields 2O(ρ(n))2^{O(\rho(n))}. The parity form (Section 2.9 and Theorem 2.2) replaces clauses by sparse polynomial equations over F2\mathbb{F}_2 and achieves 2O(ρ(n))2^{O(\rho(n))} in general. Our contributions are as follows.

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

  1. 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 2n2^n unless log⁡2(n+m)>1.03×109\log_2(n+m)>1.03\times10^9.

  1. A vanishing-product lemma (Lemma 6.2). In the clause-product scheme, each occurrence of a variable carries a polynomial “own coefficient” that equals 11 at T=0T=0; 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 qq occurrences lose their own variable, where qq is the Taylor order used there.

  1. 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 (w+1)s−1+q(w+1)s-1+q, where ss is the group size and ww the treewidth of the groups’ interaction graph. Polynomial cost therefore forces primal treewidth O(log⁡2n)O(\log^2 n), and with the preprint’s per-point evaluation and bounded occurrence it forces the formula to be a union of O(log⁡3n)O(\log^3 n)-variable pieces.

  1. Barriers (§ 8). In the same model, the clause-product scheme costs 2Ω(tw⁡)2^{\Omega(\sqrt{\operatorname{tw}})} on formulas of treewidth tw⁡\operatorname{tw}; 2Ω(n)2^{\Omega(\sqrt{n})} w.h.p. on random 3-CNF with m=Δnm=\Delta n, Δ>3\Delta>3, both after the preprint’s reduction to bounded occurrence and after its sparsification step; and 2Ω(n1/3)2^{\Omega(n^{1/3})} with the preprint’s evaluation even on path formulas.

  1. Experiments (§ 10) and code (Appendix § 15).

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 2Ω(n)2^{\Omega(\sqrt{n})} and 2O(ρ(n))2^{O(\rho(n))}, 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 kk-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 #2\#2-SAT and #3\#3-SAT, and Kutzkov [38] recently improved the bound for #3\#3-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 F2\mathbb{F}_2 it yields 2(1−ϵ)n2^{(1-\epsilon)n}-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 m/n≈4.26m/n \approx4.26 [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 nn 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 2n2^n of them, which for 100 switches is about 103010^{30}, far beyond any computer. The Exponential Time Hypothesis is the belief that nothing fundamentally better is possible: that the running time must grow like 2δn2^{\delta n} for some fixed δ>0\delta> 0, 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 2502^{50} 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 2×2502 \times2^{50} settings to try instead of 21002^{100}, 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 TT, with three properties.

  1. At T=0T = 0 the puzzle is the original one, so the recipe gives the count.

  1. At certain other dial positions the puzzle does split into small teams, apart from a little controlled leakage, described in the next subsection.

  1. The number that the recipe produces depends on the dial in a very regular way: as a polynomial in TT, 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 “(1−T)(1 - T) times switch 2, plus TT times switch 3”. At T=0T = 0 this is switch 2 itself. At T=1T = 1 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.

Diagram showing three teams connected through summary values

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 T=0T = 0, 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 dd by d+1d + 1 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 T=0T = 0. 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.

Worked example showing three dial positions, switch-rule connections, and the linear curve $5-2T$

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 5−2T5-2T; its value and slope at the split position T=1T=1 determine its value 5 at T=0T=0, which is the count of good settings.

Rewire only the second rule’s reading of switch 2, to “(1−T)(1 - T) times switch 2, plus TT times switch 3”. Running the counting recipe now gives a number that depends on the dial, namely 5−2T5 - 2T.

  • At T=0T = 0 it is 5, the true count.

  • At T=1T = 1 the second rule reads “switch 3 or switch 3”, which mentions only switch 3. The puzzle splits into the team {1,2}\{1, 2\}, whose rule has three good settings, and the team {3}\{3\}, whose rule has one. The recipe gives 3×1=33 \times1 = 3, computed as a product of two small counts.

  • The curve is a straight line, so one more fact at T=1T = 1 fixes it: its slope there, −2-2. Going back one unit along a line of slope −2-2 from height 3 reaches height 5 at T=0T = 0: 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 1−T1 - T. That weight is 1 at T=0T = 0 and 0 at T=1T = 1, 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 2n2^n at the same time, with teams that are a shrinking fraction of all the switches.

The result is a running time of 2n/f(n)2^{n/f(n)}, where f(n)f(n) grows without bound, but very slowly: roughly like the square root of the number of digits of nn, divided by a smaller correction. Because f(n)f(n) 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 1012610^{126} switches, far more than the roughly 108010^{80} 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 2cn2^{c\sqrt{n}} (§ 8); with the preprint’s way of combining teams, even a simple chain of rules costs at least 2cn1/32^{cn^{1/3}} (§ 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 ee as its satisfaction polynomial φe\varphi_e, equal to 1 when the clause is satisfied and 0 otherwise; for x1∨¬x2∨x3x_1 \lor\neg x_2 \lor x_3, φe=1−(1−x1)x2(1−x3)\varphi_e = 1 - (1-x_1)x_2(1-x_3). Then

#F=∑x∈{0,1}n∏eφe(x).(2)\#F = \sum_{x\in\{0,1\}^n}\prod_e \varphi_e(x). \tag*{(2)}

The dial replaces each input xvx_v of clause ee by a linear form ⟨Pe,v(T),x⟩\langle P_{e,v}(T),x\rangle with polynomial coefficients of degree at most RR and Pe,v(0)=evP_{e,v}(0)=e_v, giving

H(T)=∑x∈{0,1}n∏eφe(⟨Pe,v(T),x⟩v∈e′).(3)H(T)=\sum_{x\in\{0,1\}^n}\prod_e\varphi_e\left(\left\langle P_{e,v}(T),x\right\rangle_{v\in e'}\right). \tag*{(3)}

with H(0)=#FH(0)=\#F and deg⁡H≤3nR\deg H\le3nR when every variable occurs at most three times. At each point tt of a set XX of nonzero points, an (r,ε,D)(r,\varepsilon,D)-design partitions the variables into rr groups of at most 2n/r2n/r variables, assigns each clause to a group, and gives each group an integer measurement matrix. There are at most 2εn2^{\varepsilon n} measurement rows in total, shared by all clauses, and each row has coefficients whose absolute values sum to at most DD. Every clause may depend on groups other than its own only through their measurements. We say that an occurrence (e,v)(e,v) loses its own variable at tt when the coefficient of xvx_v in ⟨Pe,v(t),x⟩\langle P_{e,v}(t),x\rangle is zero; this is how a link is cut in the language above, and measurements are the second way of removing a link. H(0)H(0) is recovered by Hermite interpolation from q≈3nR/∣X∣q\approx3nR/|X| derivatives at each point; the derivatives are computed by inclusion–exclusion over sets of at most qq variables. Per point the cost is, up to polynomial factors,

∑j≤q2j(nj)⏟Taylor data×(2D+1)2εn⏟measurement readings×22n/r⏟one group.\underbrace{\sum_{j\le q}2^j\binom{n}{j}}_{\text{Taylor data}} \times \underbrace{(2D+1)^{2\varepsilon n}}_{\text{measurement readings}} \times \underbrace{2^{2n/r}}_{\text{one group}}.

with logarithm O(n[(R/∣X∣)log⁡(∣X∣/R)+εlog⁡D+1/r])O\left(n\left[(R/|X|)\log(|X|/R)+\varepsilon\log D+1/r\right]\right). The design construction (Section 2.7 of [44]) achieves

r≈log⁡n(log⁡log⁡n)2,∣X∣≈log⁡nlog⁡log⁡n,R≈log⁡n,ε≈1rlog⁡n,D≤(2n)1/128,r\approx\frac{\sqrt{\log n}}{(\log\log n)^2},\qquad|X|\approx\frac{\log n}{\log\log n},\qquad R\approx\sqrt{\log n},\qquad\varepsilon\approx\frac{1}{r\log n},\qquad D\le(2n)^{1/128},

so all three terms in the bracket are o(1)o(1) and the exponent is O(ρ(n))O(\rho(n)). General kk-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 (¬x1∨x2)∧⋯∧(¬xs∨x1)(\lnot x_1 \lor x_2) \land\cdots\land(\lnot x_s \lor x_1). 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 F2\mathbb{F}_2, 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 2O(ρ(n))2^{O(\rho(n))} for every kk-CNF (Proposition 6.4 of the preprint).

CCgeneral: Cnln⁡ln⁡n/ln⁡n<nCn\ln\ln n/\sqrt{\ln n}<n forbounded density: Cn/ln⁡n<nCn/\sqrt{\ln n}<n for
1every n>en>en>100.4n>10^{0.4}
2n>1032.2n>10^{32.2}n>101.7n>10^{1.7}
3n>10125.5n>10^{125.5}n>103.9n>10^{3.9}
5n>10555.7n>10^{555.7}n>1010.9n>10^{10.9}
10n>103517.4n>10^{3517.4}n>1043.4n>10^{43.4}
20n>1020035.2n>10^{20035.2}n>10173.7n>10^{173.7}
50n>10181955.6n>10^{181955.6}n>101085.7n>10^{1085.7}
6.0×1056.0\times10^5(not extracted)n>25.3×1011n>2^{5.3\times10^{11}} (Proposition 4.1)

Table 1. Where the bounds of Theorem 1.1 of [44], with constant CC in the exponent and natural logarithms, fall below the 2n2^n 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 nn be? The constants

All bounds in the preprint hide their constants in O(⋅)O(\cdot), and all its logarithms are natural. A subexponential bound 2Cng(n)2^{Cng(n)} with g(n)→0g(n)\to0 beats the 2n2^n of brute force only once Cg(n)<1Cg(n)<1, so where that happens depends entirely on CC.

With a hidden constant. Write u=ln⁡nu=\ln n. The general exponent of Theorem 1.1 satisfies Cnln⁡ln⁡n/ln⁡n<nCn\ln\ln n/\sqrt{\ln n}<n if and only if Cln⁡u<uC\ln u<\sqrt{u}. The function u−Cln⁡u\sqrt{u}-C\ln u decreases up to u=4C2u=4C^2 and increases after it, so for C≥2C\ge2 it has a last zero uCu_C, beyond which the general bound beats brute force for good. For C=1C=1 it is positive for every u>0u>0. The bounded-density exponent satisfies Cn/ln⁡n<nCn/\sqrt{\ln n}<n if and only if u>C2u>C^2. Table 1 lists the thresholds. Polynomial factors and the best known #3-SAT algorithms, which are much faster than 2n2^n, 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 m≤n⌈log⁡2⌈log⁡2n⌉⌉m\le n\lceil\log_2\lceil\log_2 n\rceil\rceil, the network has one vertex per clause and equality trees joining the occurrences of each variable, with every edge subdivided; it has M0≥2⋅#{occurrences}M_0\ge2\cdot\#\{\text{occurrences}\} edges, and M0=12m−6nM_0=12m-6n for a 3-CNF in which every variable occurs at least three times. The recursion is driven by explicit parameters: s=n+ms=n+m, λ=⌈log⁡2s⌉\lambda=\lceil\log_2 s\rceil, r=64r=64 groups, ε=2−17\varepsilon=2^{-17}, and u=⌈ελ⌉u=\lceil\varepsilon\lambda\rceil retained valuation levels at the root. Tracing them gives the following (proof in Appendix § 14).

Proposition 4.1. Consider such an input with n′n' occurring variables. If the root call of the recursion is active, which requires λ≥217\lambda\ge2^{17}, the running time that the proof of Theorem D.1 of [44] certifies is at least 2(K0M0+s)/λ2^{(K_0M_0+s)/\sqrt{\lambda}}, where

K0=2π24⋅217ln⁡2≈16,077.K_0=\frac{2\pi\sqrt{24\cdot2^{17}}}{\ln2}\approx16,077.

Otherwise the algorithm uses direct summation, which costs at least 2n′2^{n'}. Consequently the certified running time is at least 2n′2^{n'} unless log⁡2(n+m)>(2K0)2≈1.03×109\log_2(n+m)>(2K_0)^2\approx1.03\times10^9. For a 3-CNF with m=4.26nm=4.26n in which every variable occurs at least three times, it is at least 2n2^n unless log⁡2n>5.3×1011\log_2 n>5.3\times10^{11}; in the form 2Cn/ln⁡n2^{Cn/\sqrt{\ln n}} of Theorem 1.1 this is C≈6.0×105C\approx6.0\times10^5.

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 ss above an unstated threshold, and handles smaller sizes by direct summation. One of its stated parameter inequalities, λ4/5≤u\lambda^{4/5}\le u in (D.5), holds at the root only when log⁡2λ≥85\log_2\lambda\ge85, that is log⁡2s≥285\log_2s\ge2^{85}. For inputs of bounded density, Theorem 1.1 is therefore a statement about n→∞n\to\infty; its proof certifies no speed-up over brute force for any input that could be written down.

For the parity branch, used when m>n⌈log⁡2⌈log⁡2n⌉⌉m>n\lceil\log_2\lceil\log_2 n\rceil\rceil, the constant also depends on the constant c(k)c(k) of Section 6 of the preprint, which is not made explicit, and we do not extract it. For the interpolation exponent ρ(n)\rho(n) with constant one, Proposition B.2 in Appendix B gives the crossover: about n=102390n=10^{2390} with natural logarithms, and 2655362^{65536} with base-2 logarithms.

The clause-product scheme, abstracted

Let FF be a CNF over x1,…,xnx_1,\ldots,x_n with clauses of at most kk literals, IeI_e the variable set of clause ee, and O={(e,v):v∈Ie}O=\{(e,v):v\in I_e\} its occurrences, M=∣O∣M=|O|. Let bb bound the number of occurrences of a variable. The incidence graph GFG_F joins each clause to its variables; the primal graph Pr⁡(F)\operatorname{Pr}(F) joins two variables that share a clause.

Definition 5.1 (Clause-product interpolation scheme). A scheme for FF consists of the following.

(a) Deformation. For each occurrence o=(e,v)o=(e,v) a vector Po(T)∈Q[T]nP_o(T)\in\mathbb{Q}[T]^n of degree at most RR with Po(0)=evP_o(0)=e_v; H(T)H(T) as in (3). Its own coefficient is co(T)=(Po(T))vc_o(T)=(P_o(T))_v, a polynomial of degree at most RR with co(0)=1c_o(0)=1. Since deg⁡φe=∣Ie∣\deg\varphi_e=|I_e|, deg⁡H≤MR\deg H\le MR.

(b) Recovery. A finite set X⊂Q∖{0}X\subset\mathbb{Q}\setminus\{0\}, orders qt≥0q_t\ge0 for t∈Xt\in X, and a linear functional Λ\Lambda on Hermite data (f(j)(t))t∈X,j≤qt(f^{(j)}(t))_{t\in X,j\le q_t} with Λ(f)=f(0)\Lambda(f)=f(0) for every f∈Q[T]f\in\mathbb{Q}[T] of degree at most MRMR.

(c) Designs. For each t∈Xt\in X: a partition of [n][n] into groups St,1,St,2,…S_{t,1},S_{t,2},\ldots; a group αt(e)\alpha_t(e) for each clause; a subspace Rt,h⊆QSt,hR_{t,h}\subseteq\mathbb{Q}^{S_{t,h}} (the span of the measurement rows) for each group, such that for every clause ee, every v∈Iev\in I_e and every group h≠αt(e)h\ne\alpha_t(e),

Pe,v(t)∣St,h∈Rt,h.(4)P_{e,v}(t)|_{S_{t,h}}\in R_{t,h}. \tag*{(4)}

Write st=max⁡h∣St,h∣s_t=\max_h |S_{t,h}|, ρt=∑hdim⁡Rt,h\rho_t=\sum_h \dim R_{t,h}, and μt\mu_t for the number of measured groups (Rt,h≠0R_{t,h}\ne0). The interaction graph ItI_t has the groups as vertices; for each clause ee the groups {αt(e)}∪{h≠αt(e):Pe,v(t)∣St,h≠0\{\alpha_t(e)\}\cup\{h\ne\alpha_t(e):P_{e,v}(t)|_{S_{t,h}}\ne0 for some v∈Ie}v\in I_e\} form a clique. Let wt=tw⁡(It)w_t=\operatorname{tw}(I_t).

The clause-product form of the preprint’s interpolation algorithm (its Sections 2.1–2.8) is an instance, with Rt,hR_{t,h} the row space of its integer measurement matrix Ct,hC_{t,h} and Λ\Lambda Hermite interpolation with qt=⌈3nR/∣X∣⌉q_t=\lceil3nR/|X|\rceil (Section 2.5 of [44]). We say that o=(e,v)o=(e,v) loses its own variable at tt if co(t)=0c_o(t)=0.

What the definition does not cover

Two hypotheses carry the argument: the degree bound deg⁡H≤MR\deg H\le MR in (a), which holds because the number MM 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 M=n(log⁡n)O(1)M=n(\log n)^{O(1)} (proof of its Theorem 2.2), but the product is formed in a truncated algebra and Hermite recovery is exact only up to degree O(nR)O(nR) (its (5.5) and (3.2)). The product ∏oco\prod_o c_o of own coefficients then has degree up to MRMR, far above the degree of exactness, and the proof of Lemma 6.2 fails. The conclusion fails too in general: when MM is much larger than the exactness degree, ∑t∣Zt∣\sum_t |Z_t| can exceed ∑tqt\sum_t q_t.

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 F(0)F(0) is recovered only modulo 2p2^p, 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 2O(ρ(n))2^{O(\rho(n))} at bounded density and its weaker general bound in Section 2.8.

Cost model

We charge each point tt at least

κ(t)≥max⁡(2st, 2wt, 2min⁡(qt,⌊n/2⌋))(DP-type evaluation),\kappa(t)\ge\max\left(2^{s_t},\,2^{w_t},\,2^{\min(q_t,\lfloor n/2\rfloor)}\right) \qquad(DP\text{-type evaluation}),

and, for the preprint’s product-type evaluation, additionally κ(t)≥2ρt\kappa(t)\ge2^{\rho_t}. A scheme runs in time at most TT in this model if max⁡t∈Xκ(t)≤T\max_{t\in X}\kappa(t)\le T. 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 (≥2∣St,g∣\ge2^{|S_{t,g}|}), every tuple of measurement readings (2D+12D+1 rows ≥3ρt\ge3^{\rho_t}), and computes ∑j≤qt2j(nj)≥2min⁡(qt,⌊n/2⌋)\sum_{j\le q_t} 2^j {n\choose j}\ge2^{\min(q_t,\lfloor n/2\rfloor)} restricted sums. Every edge of ItI_t has a measured endpoint: by the definition of ItI_t, an edge joins αt(e)\alpha_t(e) or a group h≠αt(e)h\ne\alpha_t(e) with Pe,v(t)∣St,h≠0P_{e,v}(t)|_{S_{t,h}}\ne0 to such a group, and (3) makes such an hh measured. So the measured groups form a vertex cover, and since treewidth is at most the vertex-cover number [11], wt≤μt≤ρtw_t\le\mu_t\le\rho_t; 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 2wt2^{w_t} is justified for variable elimination over readings. Let M\mathcal M be the measured groups and GMG_M the torso: It[M]\mathcal{I}_t[\mathcal{M}] 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 GMG_M. A tree decomposition of GMG_M extends to It\mathcal{I}_t by attaching a bag N(h)∪{h}N(h) \cup\{h\} for each unmeasured hh, so wt≤tw⁡(GM)+1w_t \le\operatorname{tw}(G_M) + 1. Any elimination order over the readings creates a table indexed by at least tw⁡(GM)+1≥wt\operatorname{tw}(G_M) + 1 \ge w_t readings, and a nonzero measurement row takes at least two values on Boolean inputs, so it costs at least 2wt2^{w_t}. An evaluator that also counted inside groups by dynamic programming would not pay 2st2^{s_t}, and our model does not cover it.

The vanishing-product lemma

For t∈Xt \in X let Zt={o∈O:co(t)=0}Z_t = \{o \in O : c_o(t) = 0\}, the occurrences that lose their own variable at tt.

Lemma 6.1. Let o=(e,v)o = (e,v) with v∈St,hv \in S_{t,h} and h≠αt(e)h \ne\alpha_t(e). If hh is unmeasured then o∈Zto \in Z_t. If o∉Zto \notin Z_t then hh is measured and adjacent to αt(e)\alpha_t(e) in It\mathcal{I}_t.

Proof. If Rt,h=0R_{t,h} = 0, (4) forces Po(t)∣St,h=0P_o(t)|_{S_{t,h}} = 0, in particular co(t)=0c_o(t) = 0. If co(t)≠0c_o(t) \ne0 then Po(t)∣St,h≠0P_o(t)|_{S_{t,h}} \ne0, so Rt,h≠0R_{t,h} \ne0 and hh lies in the clique of ee.

Lemma 6.2 (Vanishing product). There is a point t∈Xt \in X with ∣Zt∣≤qt|Z_t| \le q_t.

Proof. Let G(T)=∏o∈Oco(T)G(T) = \prod_{o \in O} c_o(T). Then deg⁡G≤MR\deg G \le MR and G(0)=1G(0) = 1. At every t∈Xt \in X, GG vanishes to order at least ∣Zt∣|Z_t|. If ∣Zt∣≥qt+1|Z_t| \ge q_t + 1 for all tt, all Hermite data of GG are zero, so Λ\Lambda returns the same value on GG as on the zero polynomial, namely 00; but it must return G(0)=1G(0) = 1. Contradiction.

Remark 6.3. The proof uses only deg⁡G≤MR\deg G \le MR, G(0)=1G(0) = 1 and the exactness of Λ\Lambda up to degree MRMR. It applies verbatim to multi-parameter deformations T∈QdT \in\mathbb{Q}^d with any recovery set that determines f(0)f(0) for polynomials of total degree at most MRMR. It fails as soon as the exactness degree falls below deg⁡G\deg G, which is what happens in the parity form (§ 5.1).

Necessary conditions for polynomial cost

Theorem 7.1 (Structure at a point). Let tt be the point of Lemma 6.2. Then

(i) tw⁡(Pr⁡(F))≤(wt+1)st−1+qt\operatorname{tw}(\operatorname{Pr}(F)) \le(w_t + 1)s_t - 1 + q_t;

(ii) deleting at most qt+bμtstq_t + b\mu_t s_t edges of GFG_F leaves every component inside one group (with the clauses assigned to it).

Proof. (i) Let F′F' be FF with vv removed from clause ee for every (e,v)∈Zt(e,v) \in Z_t. If u,vu,v share a clause ee of F′F', their groups are equal to αt(e)\alpha_t(e) or adjacent to it by Lemma 6.1, and lie in the clique of ee, so they are equal or adjacent in It\mathcal{I}_t. Hence Pr⁡(F′)\operatorname{Pr}(F') is a subgraph of the blow-up of It\mathcal{I}_t in which each group is replaced by its variables, and replacing each group by its variables in every bag of a tree decomposition of It\mathcal{I}_t gives tw⁡(Pr⁡(F′))≤(wt+1)st−1\operatorname{tw}(\operatorname{Pr}(F')) \le(w_t + 1)s_t - 1. Every edge of Pr⁡(F)\operatorname{Pr}(F) missing from Pr⁡(F′)\operatorname{Pr}(F') is incident to a variable vv with (e,v)∈Zt(e,v) \in Z_t for some ee. There are at most ∣Zt∣≤qt|Z_t| \le q_t such variables, and adding all of them to every bag gives a tree decomposition of Pr⁡(F)\operatorname{Pr}(F) of width at most (wt+1)st−1+qt(w_t + 1)s_t - 1 + q_t.

(ii) Delete every occurrence (e,v)(e,v) with v∉St,αt(e)v \notin S_{t,\alpha_t(e)}. By Lemma 6.1 each lies in ZtZ_t or has vv in a measured group; there are at most qtq_t of the first kind and at most bμtstb\mu_t s_t 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 FF in time at most ncn^c in the cost model of § 5, with nn large.

(a) (DP-type) tw⁡(Pr⁡(F))≤(clog⁡2n+1)clog⁡2n+2c=O(log⁡22n)\operatorname{tw}(\operatorname{Pr}(F)) \le(c\log_{2}n+1)c\log_{2}n+2c=O(\log_{2}^{2}n).

(b) (Product-type) Deleting at most 2c+bc2log⁡22n2c+bc^{2}\log_{2}^{2}n edges of GFG_F leaves components of at most clog⁡2nc\log_{2}n variables. In particular, if bb is bounded, every connected component of GFG_F has O(log⁡23n)O(\log_{2}^{3}n) variables.

Proof. At the point of Lemma 6.2, 2st,2wt≤nc2^{s_t},2^{w_t}\le n^c give st,wt≤clog⁡2ns_t,w_t\le c\log_{2}n. Put j=min⁡(qt,⌊n/2⌋)j=\min(q_t,\lfloor n/2\rfloor). Then (nj)≥(n/j)j\binom{n}{j}\ge(n/j)^j, which is at least nj/2n^{j/2} if j≤nj\le\sqrt n and at least 2j≥2n2^j\ge2^{\sqrt n} otherwise. So (nj)≤nc\binom{n}{j}\le n^c forces j≤2cj\le2c, hence j<⌊n/2⌋j<\lfloor n/2\rfloor for large nn and qt=j≤2cq_t=j\le2c. Theorem 7.1(i) gives (a). For (b), μt≤ρt≤clog⁡2n\mu_t\le\rho_t\le c\log_{2}n, and Theorem 7.1(ii) deletes at most 2c+bc2log⁡22n2c+bc^2\log_{2}^{2}n edges. Deleting jj edges from a connected graph leaves at most j+1j+1 components.

Exact counting runs in time 2O(tw⁡)poly⁡(n)2^{O(\operatorname{tw})}\operatorname{poly}(n) by dynamic programming over a tree decomposition [26, 46], which is polynomial for treewidth O(log⁡n)O(\log n). So a scheme of this kind cannot be polynomial on any family of treewidth ω(log⁡22n)\omega(\log_{2}^{2}n). Between ω(log⁡n)\omega(\log n) and O(log⁡22n)O(\log_{2}^{2}n), where treewidth dynamic programming is not polynomial, our bounds leave open whether such a scheme can be.

Corollary 7.3 (Paths). Let Pn=⋀i<n(xi∨¬xi+1)P_n=\bigwedge_{i<n}(x_i\vee\neg x_{i+1}), which is countable in linear time. In the cost model, every product-type scheme on PnP_n costs at least 2min⁡(n/2−1,(n/4)1/3)=2Ω(n1/3)2^{\min(\sqrt{n/2}-1,(n/4)^{1/3})}=2^{\Omega(n^{1/3})}.

Proof. GPnG_{P_n} is a path, so leaving components of at most ss variables needs at least ⌈n/s⌉−1\lceil n/s\rceil-1 deletions, and b=2b=2. At the point of Lemma 6.2, q+2μs≥n/s−1q+2\mu s\ge n/s-1. If q≥n/(2s)−1q\ge n/(2s)-1 the Taylor factor is at least (nmin⁡(q,⌊n/2⌋))≥2min⁡(q,⌊n/2⌋)\binom{n}{\min(q,\lfloor n/2\rfloor)}\ge2^{\min(q,\lfloor n/2\rfloor)} and, with 2s2^s, the cost is at least 2n/2−12^{\sqrt{n/2}-1}. Otherwise μ≥n/(4s2)\mu\ge n/(4s^2) and max⁡(2s,2μ)≥2(n/4)1/3\max(2^s,2^\mu)\ge2^{(n/4)^{1/3}}.

The preprint’s per-point evaluation is therefore super-polynomial even where counting is trivial; its gain over 2n2^n 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 FF costs at least

2min⁡((tw⁡(Pr⁡(F))+1)/2−1,  (tw⁡(Pr⁡(F))+1)/2,  ⌊n/2⌋).2^{\min\left(\sqrt{(\operatorname{tw}(\operatorname{Pr}(F))+1)/2}-1,\;(\operatorname{tw}(\operatorname{Pr}(F))+1)/2,\;\lfloor n/2\rfloor\right)}.

Proof. Write τ=tw⁡(Pr⁡(F))\tau=\operatorname{tw}(\operatorname{Pr}(F)). At the point of Lemma 6.2, (wt+1)st≥τ+1−qt(w_t+1)s_t\ge\tau+1-q_t. If qt≥(τ+1)/2q_t\ge(\tau+1)/2, the Taylor factor is at least (nmin⁡(qt,⌊n/2⌋))≥2min⁡(qt,⌊n/2⌋)\binom{n}{\min(q_t,\lfloor n/2\rfloor)}\ge2^{\min(q_t,\lfloor n/2\rfloor)}. Otherwise (wt+1)st≥(τ+1)/2(w_t+1)s_t\ge(\tau+1)/2, so max⁡(st,wt+1)≥(τ+1)/2\max(s_t,w_t+1)\ge\sqrt{(\tau+1)/2}.

Lemma 8.2. Let FF be a uniformly random 3-CNF with nn variables and m=Δnm=\Delta n clauses, Δ>3\Delta>3. With high probability tw⁡(Pr⁡(F))≥cΔn\operatorname{tw}(\operatorname{Pr}(F))\ge c_\Delta n for a constant cΔ>0c_\Delta>0.

Proof. Two facts hold with high probability (proofs in Appendix § 13). (1) Every set of between n/3n/3 and 2n/32n/3 variables shares a clause with its complement in at least m/3m/3 clauses. (2) Every set of jj variables occurs in at most CΔjlog⁡(en/j)C_\Delta j\log(en/j) clauses. A graph of treewidth τ\tau has a separator YY with ∣Y∣≤τ+1|Y|\le\tau+1 whose removal leaves components of at most n/2n/2 vertices. If ∣Y∣≤n/9|Y|\le n/9, take AA to be the largest component if it has at least n/3n/3 vertices, and otherwise a union of components grown one at a time until it reaches n/3n/3; in both cases n/3≤∣A∣≤2n/3n/3 \le|A| \le2n/3. No clause meets two components, so every clause meeting both AA and its complement contains a variable of YY. By (1) and (2), m/3≤CΔ∣Y∣log⁡(en/∣Y∣)m/3 \le C_{\Delta}|Y|\log(en/|Y|), which forces ∣Y∣≥cΔn|Y| \ge c_{\Delta}n.

Theorem 8.3 (Random 3-CNF). Let FF be uniformly random with m=Δnm=\Delta n clauses, Δ>3\Delta>3. With high probability the clause-product scheme costs 2Ω(n)2^{\Omega(\sqrt{n})} on FF in the cost model:

(a) applied to the preprint’s bounded-occurrence formula F⋆F^\star (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 F⋆F^\star to a vertex turns Pr⁡(F⋆)\operatorname{Pr}(F^\star) into a graph containing Pr⁡(F)\operatorname{Pr}(F), so Pr⁡(F)\operatorname{Pr}(F) is a minor of Pr⁡(F⋆)\operatorname{Pr}(F^\star) and tw⁡(Pr⁡(F⋆))≥cΔn\operatorname{tw}(\operatorname{Pr}(F^\star)) \ge c_{\Delta}n by Lemma 8.2. F⋆F^\star has O(n)O(n) variables; apply Theorem 8.1. (b) The preprint’s rule A.1 fixes an integer M≥2M \ge2 and thresholds θj=Mj\theta_j=M^j. It branches on a nonempty proper subset AA of a width-cc clause when AA lies in at least θc−∣A∣\theta_{c-|A|} width-cc clauses, choosing the smallest cc and then the largest ∣A∣|A|. Its first child is G∧AG \land A, where GG is the set of the other clauses, so the clauses containing AA are replaced by the single clause AA; there is no unit propagation. The parameter search sets M≥1/σM \ge1/\sigma, so M≥3M \ge3 once σ≤1/3\sigma\le1/3. Follow first children only. W.h.p. no pair of literals lies in three clauses, so no pair reaches θ1=M≥3\theta_1=M \ge3, and the first sets that fire are single literals ℓ\ell whose current degree is at least θ2=M2\theta_2=M^2. Each adds the unit {ℓ}\{\ell\} and removes the clauses containing ℓ\ell. 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 θ2\theta_2 in FF (a current degree never exceeds the original one). The leaf therefore contains every clause of FF without such a literal, plus unit clauses. W.h.p. the clauses with such a literal number at most η(θ2)n\eta(\theta_2)n with η→0\eta\to0 as θ2→∞\theta_2 \to\infty, and θ2=M2\theta_2=M^2 grows as σ→0\sigma\to0. 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 (cΔ−3η)n(c_{\Delta}-3\eta)n, 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 2Ω(n)2^{\Omega(\sqrt{n})} (Theorem 8.3) and the preprint’s 2O(ρ(n))2^{O(\rho(n))}, in the cost model. Our lower-bound technique cannot exceed 2O(n)2^{O(\sqrt{n})}: its only constraint is (w+1)s+q≳tw(w+1)s+q \gtrsim tw, which s=w=q=ns=w=q=\sqrt{n} satisfies. Narrowing the gap needs one of two new ingredients. From above, a design on an expander with n\sqrt{n} groups, O(n)O(\sqrt{n}) interaction width, Taylor order O(n)O(\sqrt{n}) and O(1)O(1) or polylogarithmically many rows per measured group would bring the scheme to 2O~(n)2^{\widetilde{O}(\sqrt{n})}. From below, one must show that measurements cannot absorb the cut. A measured group of dimension one can absorb two foreign occurrences (e,v),(e′,v′)(e,v),(e',v') with v≠v′v \ne v' at tt only if the 2×22 \times2 minor ce,v(t)ce′,v′(t)−pe,v,v′(t)pe′,v′,v(t)c_{e,v}(t)c_{e',v'}(t)-p_{e,v,v'}(t)p_{e',v',v}(t) vanishes; that polynomial equals 11 at T=0T=0, so each such pair is absorbed at no more than 2R2R 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 ω(log⁡2n)\omega(\log^2 n), 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. H(0)H(0) 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 TT near tt, it would hold identically in TT and hence at T=0T=0, forcing ev∈Rt,he_v \in R_{t,h} for every foreign variable, that is, measuring the cut variables one by one. So the design cannot be extended to a neighbourhood of tt. 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: K0≈16,077.4K_0 \approx16{,}077.4 bits per edge at the root, and 18,534.8 if every level of the recursion shrinks by exactly the guaranteed factor 3/323/32. For 3-CNF at density 4.26 (about 45 network edges per variable) the certified exponent is at least 725,416 n/log⁡2s725{,}416\,n/\sqrt{\log_2 s} bits, and about 836,293 n/log⁡2s836{,}293\,n/\sqrt{\log_2 s} over all levels. It also counts the mode tuples of (D.14) exactly by a generating-function recurrence, for NN variables of each weight and budget pp: for (N,p)=(2,200)(N,p)=(2,200), (6,300)(6,300) and (6,600)(6,600) the natural logarithm of the count is 0.866, 0.871 and 0.901 of the estimate 2πpN/62\pi\sqrt{pN/6} 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 R∈{1,2}R \in\{1,2\}, and MR+1MR+1 evaluation points, we computed H(t)H(t) exactly by summing (3) over all assignments and recovered H(0)H(0) by Lagrange interpolation. In 30 of 30 cases H(0)H(0) equals the brute-force count #F\#F, 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.

nnminimal log⁡2\log_{2} costn1/3n^{1/3}
10210^{2}4.04.6
10310^{3}8.010.0
10410^{4}18.021.5
10510^{5}37.046.4
10610^{6}80.0100.0

caption:

:::

The fitted exponent of nn is 0.327, against 1/3 in Corollary 7.3; the path itself is counted in linear time by a 2×22 \times2 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.

familynntw ≥\geq (MMW)tw ≤\leq (min-fill)bound (bits)at min-fill width
uf20-912012.914.84.04.0
uf50-2185019.433.84.46.0
uf75-3257523.050.85.07.0
uf100-43010027.067.85.08.0
uf125-53812529.885.35.69.0
uf150-64515032.4102.86.010.0
uf175-75317534.9119.46.011.0
uf200-86020037.1135.36.011.8
uf225-96022538.9153.96.012.0
uf250-106525040.7170.96.013.0

Table 1 (PDF p. 15).

The min-fill widths grow linearly, about 0.68n0.68n, 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 tw\sqrt{\mathrm{tw}} scaling: at the min-fill width the bound grows from 4 to 13 bits as nn 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 n=20n = 20 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 2342^{34} entries, and brute force needs 2502^{50} 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 F2\mathbb{F}_{2}, 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 PVPV 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, 2O(nlog⁡log⁡n/log⁡n)2^{O(n \log\log n/\sqrt{\log n})}, is subexponential as n→∞n \to\infty; by itself it says nothing about any fixed nn, because the preprint states no constants. With a hidden constant of 3 it beats brute force only beyond n≈10126n \approx10^{126}, and with 10 only beyond 10351710^{3517} (Table 1). Extracting the constants from its tensor-contraction proof, the running time it certifies for inputs of bounded density stays above 2n2^n unless log⁡2(n+m)>109\log_2(n+m) > 10^9, and on random 3-CNF at the satisfiability threshold unless log⁡2n>5×1011\log_2 n > 5 \times10^{11} (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 O(log⁡2n)O(\log^2 n), costs 2Ω(n)2^{\Omega(\sqrt{n})} on random 3-CNF, and in the preprint’s form is super-polynomial even on paths. The gap between 2Ω(n)2^{\Omega(\sqrt{n})} and 2O(ρ(n))2^{O(\rho(n))} 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 FF have nn variables and m=Δnm = \Delta n clauses, each on three distinct uniformly random variables with random signs.

Lemma A.1. If Δ>3\Delta> 3, then w.h.p. every set SS of variables with n/3≤∣S∣≤2n/3n/3 \le|S| \le2n/3 shares at least m/3m/3 clauses with its complement.

Proof. For ∣S∣=αn|S| = \alpha n a random clause lies inside SS or inside its complement with probability at most α3+(1−α)3≤1/3\alpha^3 + (1 - \alpha)^3 \le1/3, so the number of crossing clauses dominates Bin⁡(m,2/3)\operatorname{Bin}(m, 2/3), which falls below m/3m/3 with probability at most e−mKL⁡(1/3∥2/3)=2−m/3e^{-m\operatorname{KL}(1/3\mathbin{\|}2/3)} = 2^{-m/3}. A union bound over at most 2n2^n sets gives 2n−Δn/3→02^{n-\Delta n/3} \to0. □

Lemma A.2. W.h.p., for every j≥1j \ge1, every set of jj variables occurs in at most CΔjlog⁡(en/j)C\Delta j\log(en/j) clauses.

Proof. For a fixed jj-set SS, the number of variables of SS in one clause is hypergeometric (three draws without replacement), so its moment generating function is at most that of Bin⁡(3,j/n)\operatorname{Bin}(3,j/n) ([31], Theorem 4). The clauses are independent, so the number of occurrences satisfies the Chernoff bound of Bin⁡(3m,j/n)\operatorname{Bin}(3m,j/n), whose mean is 3Δj3\Delta j: it exceeds tt with probability at most (3eΔj/t)t(3e\Delta j/t)^t. Take t=Cjlog⁡(en/j)t = Cj\log(en/j) with C≥3e2ΔC \ge3e^2\Delta: this is at most e−te^{-t}, and a union bound over (nj)≤(en/j)j\binom{n}{j} \le(en/j)^j sets gives (en/j)j(1−C)(en/j)^{j(1-C)}, which sums to o(1)o(1) over jj. □

The constants

Proof of Proposition 4.1

We use the notation of Appendix D of [44]. For an input with m≤n⌈log⁡2⌈log⁡2n⌉⌉m \le n\lceil\log_2\lceil\log_2 n\rceil\rceil the algorithm builds the clause network of its Section D.2 and applies Theorem D.1 with s=n+ms = n + m. Each clause port is joined to the equality structure of its variable, which for a variable with dd ports has 11, 22 or 2d−32d - 3 edges when d=1d = 1, d=2d = 2 or d≥3d \ge3; each is at least dd. Every edge is then subdivided once. So M0≥2∑vdv=2⋅{occurrences}≥2n′M_0 \ge2\sum_v d_v = 2\cdot\{\text{occurrences}\} \ge2n', and M0=2∑v(2dv−3)=12m−6nM_0 = 2\sum_v(2d_v - 3) = 12m - 6n for a 3-CNF in which every variable occurs at least three times.

Write λ=⌈log⁡2s⌉\lambda= \lceil\log_2 s\rceil and ϵ=2−17\epsilon= 2^{-17}, so the root call retains u=⌈ϵλ⌉u = \lceil\epsilon\lambda\rceil valuation levels ((D.4)). If u=0u = 0, that is λ<217\lambda< 2^{17}, the root cannot be an active call, since Lemma D.5 needs u≥1u \ge1; the preprint then uses direct summation, which costs at least 2n′2^{n'}. If M0≤HℓM_0 \le H_\ell, where Hℓ=⌈s/λ⌉H_\ell= \lceil s/\sqrt{\lambda}\rceil is the leaf threshold of (D.4), the root is a leaf and direct summation over its M0≥2n′M_0 \ge2n' edges costs at least 2n′2^{n'}. These are the cases of the proposition in which the root is not active.

Otherwise the root is active. Fix an interpolation node tt with qt>0q_t > 0, write i=v2(t)<ui = v_2(t) < u, Dt=L/2iD_t = L/2^i, and M=M0M = M_0. By Lemma D.5, pt=p+8hDt+8M(a+1)≥8hDtp_t = p + 8hD_t + 8M(a + 1) \ge8hD_t with h=⌈3M/u⌉≥3M/uh = \lceil3M/u \rceil\ge3M/u, so pt≥24MDt/up_t \ge24MD_t/u. The proof bounds the number of tuples satisfying (D.14) by

exp⁡(θpt+6MDt∑j≥1−ln⁡(1−e−θj))\exp\left(\theta p_t + \frac{6M}{D_t}\sum_{j\ge1} -\ln(1-e^{-\theta j})\right)

with 6M/Dt6M/D_t the number of mode variables of each weight from (D.13), and then uses ∑j≥1−ln⁡(1−e−θj)≤π2/(6θ)\sum_{j\ge1} -\ln(1-e^{-\theta j}) \le\pi^2/(6\theta). For every θ>0\theta> 0 the resulting estimate satisfies

θpt+π2MDtθ≥2πMptDt≥2π24Mu≥2π24M0ελ,\theta p_t + \frac{\pi^2M}{D_t\theta} \ge2\pi\sqrt{\frac{Mp_t}{D_t}} \ge2\pi\sqrt{24}\frac{M}{\sqrt{u}} \ge2\pi\sqrt{24}\frac{M_0}{\sqrt{\varepsilon\lambda}},

by the inequality of arithmetic and geometric means, pt≥24MDt/up_t \ge24MD_t/u and u≤ελu \le\varepsilon\lambda. Each tuple produces child contractions, so the certified number of calls is at least this exponential, and every leaf is charged 2Hℓ2^{H_\ell} with Hℓ≥s/λH_\ell\ge s/\sqrt{\lambda}. Converting to base two, the certified running time is at least 2(K0M0+s)/λ2^{(K_0M_0+s)/\sqrt{\lambda}} with K0=2π24⋅217/ln⁡2K_0 = 2\pi\sqrt{24}\cdot2^{17}/\ln2.

For the consequences, (K0M0+s)/λ>2K0n′/λ(K_0M_0+s)/\sqrt{\lambda} > 2K_0n'/\sqrt{\lambda}, which is at least n′n' unless λ>(2K0)2≈1.034×109\lambda> (2K_0)^2 \approx1.034 \times10^9. For a 3-CNF with m=αnm = \alpha n and every variable occurring at least three times, the exponent is (K0(12α−6)+1+α)n/λ(K_0(12\alpha-6)+1+\alpha)n/\sqrt{\lambda}; at α=4.26\alpha= 4.26 the coefficient is 725,416, so the bound is below 2n2^n only if λ>5.26×1011\lambda> 5.26 \times10^{11}. Since n/log⁡2n=ln⁡2 n/ln⁡nn/\sqrt{\log_2 n} = \sqrt{\ln2}\,n/\sqrt{\ln n}, this is C=725,416ln⁡2≈6.0×105C = 725,416\sqrt{\ln2} \approx6.0 \times10^5 in the form 2Cn/ln⁡n2^{Cn/\sqrt{\ln n}}.

Remark B.1. The argument keeps only the root, the dominant term of ptp_t and the leaf charge, so it understates the certified bound. The preprint’s choice θ=M/(Dtpt)\theta= \sqrt{M/(D_tp_t)} gives the factor 1+π21+\pi^2 in place of 2π2\pi, about 1.7 times larger, and the deeper levels add about 15% (experiment E5). The parameter inequality λ4/5≤u\lambda^{4/5} \le u of (D.5), on which the precision estimate (D.11) rests, requires λ4/5≤λ/217\lambda^{4/5} \le\lambda/2^{17} at the root, that is log⁡2λ≥85\log_2\lambda\ge85.

The interpolation exponent with constant one

The interpolation algorithm runs in time 2O(ρ(n))2^{O(\rho(n))} up to polynomial factors. We ask when ρ(n)<n\rho(n) < n, taking the bound literally with constant one, first with the preprint’s natural logarithms and then with base-2 logarithms.

Proposition B.2. (i) ρ(n)=n(ln⁡ln⁡n)2/ln⁡n\rho(n) = n(\ln\ln n)^2/\sqrt{\ln n} satisfies ρ(n)≥n\rho(n) \ge n if and only if eeu1≤n≤eeu2e^{e^{u_1}} \le n \le e^{e^{u_2}}, where u1≈1.4296u_1 \approx1.4296 and u2≈8.6132u_2 \approx8.6132 are the solutions of u=4ln⁡uu = 4\ln u. Numerically, ρ(n)≥n\rho(n) \ge n for every integer 66≤n≤10239066 \le n \le10^{2390}, since eeu1≈65.2e^{e^{u_1}} \approx65.2 and eeu2≈102390.2e^{e^{u_2}} \approx10^{2390.2}.

(ii) With base-2 logarithms, ρ2(n)=n(log⁡2log⁡2n)2/log⁡2n\rho_2(n) = n(\log_2\log_2 n)^2/\sqrt{\log_2 n} satisfies ρ2(n)<n\rho_2(n) < n if and only if n<n1n < n_1 or n>265536n > 2^{65536}, where n1=22a1≈5.14n_1 = 2^{2^{a_1}} \approx5.14 and a1≈1.2396a_1 \approx1.2396 is the smaller solution of a=4log⁡2aa = 4\log_2 a. Moreover ρ2(265536)=265536\rho_2(2^{65536}) = 2^{65536}.

Proof. (i) For n>en > e put u=ln⁡ln⁡n>0u = \ln\ln n > 0, so that n=eeun = e^{e^u}, an increasing function of uu. Then

ρ(n)<n⟺(ln⁡ln⁡n)2<ln⁡n⟺u2<eu/2⟺2ln⁡u<u2⟺g(u)>0,\rho(n) < n \Longleftrightarrow(\ln\ln n)^2 < \sqrt{\ln n} \Longleftrightarrow u^2 < e^{u/2} \Longleftrightarrow2\ln u < \frac{u}{2} \Longleftrightarrow g(u) > 0,

with g(u)=u−4ln⁡ug(u) = u - 4\ln u. Since g′(u)=1−4/ug'(u) = 1 - 4/u, gg decreases on (0,4](0,4] and increases on [4,∞)[4,\infty), with g(1)=1>0g(1) = 1 > 0, g(4)=4−4ln⁡4<0g(4) = 4 - 4\ln4 < 0 and g(20)=20−4ln⁡20>0g(20) = 20 - 4\ln20 > 0: there are exactly two zeros, u1∈(1,4)u_1 \in(1,4) and u2∈(4,20)u_2 \in(4,20), and g<0g < 0 exactly between them. Bisection gives u1≈1.4296u_1 \approx1.4296 and u2≈8.6132u_2 \approx8.6132, so eeu2≈5503.66e^{e^{u_2}} \approx5503.66 and eeu2=105503.66/ln⁡10≈102390.2e^{e^{u_2}} = 10^{5503.66/\ln10} \approx10^{2390.2}. For 2<n≤e2 < n \le e we have ∣ln⁡ln⁡n∣<0.37|\ln\ln n| < 0.37 and ln⁡n>0.83\sqrt{\ln n} > 0.83, so ρ(n)<0.17n<n\rho(n) < 0.17n < n; these nn do not affect the integer range stated.

(ii) The same argument with a=log⁡2log⁡2na = \log_{2}\log_{2} n gives ρ2(n)<n⟺a2<2a/2⟺f(a)>0\rho_{2}(n) < n \Longleftrightarrow a^{2} < 2^{a/2} \Longleftrightarrow f(a) > 0 with f(a)=a−4log⁡2af(a) = a - 4\log_{2} a. Here f′(a)=1−4/(aln⁡2)f'(a) = 1 - 4/(a\ln2), so ff decreases on (0,4/ln⁡2](0,4/\ln2] and increases after, with f(1)=1>0f(1) = 1 > 0, f(2)=−2<0f(2) = -2 < 0 and f(16)=16−4⋅4=0f(16) = 16 - 4\cdot4 = 0. So its zeros are a1∈(1,2)a_{1} \in(1,2) and a2=16a_{2} = 16, and ρ2(n)<n\rho_{2}(n) < n exactly when n<22a1n < 2^{2^{a_{1}}} or n>2216=265536n > 2^{2^{16}} = 2^{65536}. At a=16a = 16 both sides of a2<2a/2a^{2} < 2^{a/2} equal 256. Bisection gives a1≈1.2396a_{1} \approx1.2396.

The number 2655362^{65536} has ⌊65536log⁡102⌋+1=19,729\lfloor65536\log_{10}2\rfloor+ 1 = 19{,}729 decimal digits. Neither crossover says anything about running times: the preprint does not state the constant, and with constant CC 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.901

References

  1. [1]A. Abboud, R. Williams, H. Yu. More applications of the polynomial method to algorithm design. SODA 2015.
  2. [2]M. Alekhnovich, A. Razborov. Lower bounds for polynomial calculus: non-binomial case. Proc. Steklov Inst. Math. 242, 2003.
  3. [3]J. Alman. Limits on the universal method for matrix multiplication. CCC 2019.arxiv.org/abs/1812.08731
  4. [4]J. Alman, V. Vassilevska Williams. Limits on all known (and some unknown) approaches to matrix multiplication. FOCS 2018.
  5. [5]A. Ambainis, Y. Filmus, F. Le Gall. Fast matrix multiplication: limitations of the Coppersmith–Winograd method. STOC 2015.
  6. [6]E. Ben-Sasson, R. Impagliazzo. Random CNF’s are hard for the polynomial calculus. Comput. Complexity 19, 2010.
  7. [7]E. Ben-Sasson, A. Wigderson. Short proofs are narrow—resolution made simple. J. ACM 48(2), 2001.
  8. [8]A. Björklund. Determinant sums for undirected Hamiltonicity. FOCS 2010.
  9. [9]A. Björklund, T. Husfeldt, M. Koivisto. Set partitioning via inclusion–exclusion. SIAM J. Comput. 39(2), 2009.DOI
  10. [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. [11]H. L. Bodlaender. A tourist guide through treewidth. Acta Cybernetica 11, 1993.
  12. [12]H. L. Bodlaender, A. M. C. A. Koster. Treewidth computations I. Upper bounds. Inform. and Comput. 208(3), 2010.DOI
  13. [13]H. L. Bodlaender, A. M. C. A. Koster. Treewidth computations II. Lower bounds. Inform. and Comput. 209(7), 2011.
  14. [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. [15]A. A. Bulatov. A dichotomy theorem for nonuniform CSPs. FOCS 2017.arxiv.org/abs/1703.03021
  16. [16]C. Calabro. The exponential complexity of satisfiability problems. PhD thesis, UC San Diego, 2009.
  17. [17]C. Calabro, R. Impagliazzo, R. Paturi. A duality between clause width and clause density for SAT. CCC 2006.DOI
  18. [18]M. Christandl, P. Vrana, J. Zuiddam. Barriers for fast matrix multiplication from irreversibility. CCC 2019.
  19. [19]V. Chvátal, E. Szemerédi. Many hard examples for resolution. J. ACM 35(4), 1988.DOI
  20. [20]S. A. Cook. Feasibly constructive proofs and the propositional calculus. STOC 1975.DOI
  21. [21]J. M. Crawford, L. D. Auton. Experimental results on the crossover point in random 3-SAT. Artificial Intelligence 81, 1996.DOI
  22. [22]R. Curticapean. Block interpolation: a framework for tight exponential-time counting complexity. Inform. and Comput. 261, 2018.
  23. [23]V. Dahllöf, P. Jonsson, M. Wahlström. Counting models for 2SAT and 3SAT formulae. Theoret. Comput. Sci. 332, 2005.DOI
  24. [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. [25]I. Dinur. Improved algorithms for solving polynomial systems over GF(2) by multiple parity-counting. SODA 2021.arxiv.org/abs/2005.04800
  26. [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. [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. [28]V. Gogate, R. Dechter. A complete anytime algorithm for treewidth. UAI 2004.arxiv.org/abs/1207.4109
  29. [29]T. D. Hansen, H. Kaplan, O. Zamir, U. Zwick. Faster k-SAT algorithms using biased-PPSZ. STOC 2019.DOI
  30. [30]T. Hertli. 3-SAT faster and simpler—unique-SAT bounds for PPSZ hold in general. SIAM J. Comput. 43(2), 2014.
  31. [31]W. Hoeffding. Probability inequalities for sums of bounded random variables. J. Amer. Statist. Assoc. 58(301), 1963.
  32. [32]J. Holmgren, A. S. Wein. Counterexamples to the low-degree conjecture. ITCS 2021.
  33. [33]H. H. Hoos, T. Stützle. SATLIB: an online resource for research on SAT. In SAT 2000, IOS Press, 2000.
  34. [34]S. B. Hopkins. Statistical inference and the sum of squares method. PhD thesis, Cornell University, 2018.DOI
  35. [35]R. Impagliazzo, R. Paturi. On the complexity of k-SAT. J. Comput. System Sci. 62(2), 2001.DOI
  36. [36]R. Impagliazzo, R. Paturi, F. Zane. Which problems have strongly exponential complexity? J. Comput. System Sci. 63(4), 2001.
  37. [37]I. Koutis. Faster algebraic algorithms for path and packing problems. ICALP 2008.DOI
  38. [38]K. Kutzkov. Complementary branching for #SAT: bounded-degree bounds and faster #3-SAT. IJCAI 2026.DOI
  39. [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. [40]J.-M. Lagniez, P. Marquis. An improved decision-DNNF compiler. IJCAI 2017.DOI
  41. [41]C. Lee, J. Lee, S. Oum. Rank-width of random graphs. J. Graph Theory 70(3), 2012.
  42. [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. [43]D. Mitchell, B. Selman, H. Levesque. Hard and easy distributions of SAT problems. AAAI 1992.
  44. [44]OpenAI. The exponential time hypothesis is false. Preprint, 17 October 2026, revised 25 October 2026.hub.valency.io/works/W_h8uqubsk
  45. [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. [46]M. Samer, S. Szeider. Algorithms for propositional model counting. J. Discrete Algorithms 8(1), 2010.
  47. [47]D. Scheder. PPSZ is better than you think. TheoretICCS 3, 2024.
  48. [48]U. Schöning. A probabilistic algorithm for k-SAT and constraint satisfaction problems. FOCS 1999.
  49. [49]M. Thurley. sharpSAT—counting models with advanced component caching and implicit BCP. SAT 2006.
  50. [50]C. A. Tovey. A simplified NP-complete satisfiability problem. Discrete Appl. Math. 8, 1984.DOI
  51. [51]L. G. Valiant. The complexity of computing the permanent. Theoret. Comput. Sci. 8, 1979.DOI
  52. [52]V. Vassilevska Williams. On some fine-grained questions in algorithms and complexity. Proc. ICM 2018.DOI
  53. [53]M. Wahlström. A tighter bound for counting max-weight solutions to 2SAT instances. IWPEC 2008.DOI
  54. [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. [55]R. Williams. Faster all-pairs shortest paths via circuit complexity. STOC 2014.
  56. [56]D. Zhuk. A proof of the CSP dichotomy conjecture. J. ACM 67(5), 2020.

Paper details

vlnc:W_vxvepgk2
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY-SA 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents