Counting solutions faster than the Exponential Time Hypothesis allows

← All digests

Family 378 · Theoretical computer science
Importance 5/5 · Provisional editorial rating
Sources consulted 2026-10-27

1. The question

Suppose a system has a million yes-or-no choices and a list of conditions involving small groups of those choices. Can we determine whether all the conditions can hold simultaneously? Can we count every successful choice without examining every possibility?

Boolean satisfiability turns this question into a precise mathematical problem. Trying all assignments to $n$ variables takes roughly $2^n$ steps. Decades of algorithms have reduced the base of that exponential for important versions of the problem. The Exponential Time Hypothesis, or ETH, predicts that a genuinely subexponential algorithm for three-literal satisfiability is impossible.

Family 378 claims such an algorithm, and more: it counts all satisfying assignments exactly, deterministically, using polynomial memory. Its exponent grows more slowly than $n$. The claimed advance would therefore cross the boundary that ETH was introduced to describe.

2. Background and essential definitions

Formulas and their solutions

A Boolean variable takes the value zero or one. A literal is a variable or its negation; a clause is an OR of literals. A formula in conjunctive normal form, abbreviated CNF, is an AND of clauses. A $k$-CNF has at most $k$ literals in each clause.

For example,

$$F(x,y)=(x\lor y)\land(\neg x\lor y)$$

has exactly two satisfying assignments: $(0,1)$ and $(1,1)$. Both clauses hold precisely when $y=1$, while $x$ is free. The symbols $\lor$, $\land$, and $\neg$ mean OR, AND, and NOT.

The decision problem asks whether a satisfying assignment exists. The counting problem asks for

$$\#F=\bigl|\{x\in\{0,1\}^n:F(x)=1\}\bigr|.$$

Knowing the count solves the decision problem by testing whether it is positive. The reverse direction is substantially less direct: even 2-SAT, whose decision version has a polynomial-time algorithm, has a difficult exact-counting version.

What “subexponential” means

Here $n$ is the number of declared variables, $m$ the number of clauses, and $k$ a fixed constant. Polynomial factors in the input size are allowed. A bound $2^{o(n)}$ means that its base-two logarithm, divided by $n$, tends to zero.

For example, $1.1^n$ remains exponential: its exponent is a fixed positive multiple of $n$. In contrast, $2^{n/\sqrt{\log n}}$ is subexponential. It can still be enormous. A subexponential upper bound alone does not give a polynomial-time algorithm.

ETH asserts a positive exponential barrier for worst-case 3-SAT. Its stronger relative, SETH, predicts that as the fixed clause width increases, the best exponential rate approaches exhaustive search. These are quantitative assumptions about running time, beyond the usual question of whether polynomial time is possible.

3. Development history and previous partial results

The class NP consists of decision problems whose positive answers have certificates checkable in polynomial time. The theory of NP-completeness established satisfiability as a universal encoding of these problems. It compares them through polynomial-size transformations. ETH arose from asking a finer question: which transformations preserve a linear scale in the exponent?

Impagliazzo and Paturi’s 2001 paper studied the dependence of satisfiability complexity on clause width. Impagliazzo, Paturi and Zane developed reductions suited to exponential complexity, including the sparsification lemma. Roughly, sparsification expresses a formula through a controlled collection of formulas with few clause occurrences per variable. Its counting version arranges that different branches have disjoint solution sets, so their counts can be added.

Earlier algorithms had already beaten brute force. Schöning’s 1999 randomized algorithm repeatedly repairs an unsatisfied clause by randomly flipping one of its variables. For 3-SAT its guarantee has exponential factor $(4/3)^n$. The PPSZ approach instead processes variables in a random order, using logical deductions when possible and guesses otherwise. Later analyses improved its exponential rate; Scheder’s 2024 work obtained further gains without changing the algorithm itself. These improvements leave a fixed positive coefficient multiplying $n$ in the exponent.

Exact counting developed alongside decision algorithms. Branching, inclusion–exclusion, and algebraic methods improved its running times, but the counting analogue of ETH still predicted an unavoidable exponential cost. Practical SAT solvers supplied another kind of progress: they could handle many structured instances without providing subexponential worst-case guarantees.

ETH and SETH consequently became foundations for conditional lower bounds in parameterized and fine-grained complexity. Such results explain why a particular dependence on a parameter, or a quadratic running time, may be difficult to improve. Family 378 addresses the fixed-width SAT assumption underlying many of those explanations.

4. What the new manuscripts claim

Exact counting with polynomial memory

Theorem 1.1 of the October 25 manuscript states that, for every fixed $k\ge2$, a deterministic algorithm computes $\#F$ in

$$(n+m)^{O_k(1)} 2^{O_k\!\left(n\log\log n/\sqrt{\log n}\right)}$$

bit operations, using $(n+m)^{O_k(1)}$ bits of memory. The subscript $k$ permits constants to depend on the fixed width. Logarithms are natural here; changing their base only affects constants. The statement is formulated for $n\ge20$, with smaller inputs handled directly.

When the clause density is bounded, meaning $m\le Dn$ for a fixed constant $D>0$, the claimed running time improves to

$$(n+m)^{O_{k,D}(1)} 2^{O_{k,D}\!\left(n/\sqrt{\log n}\right)}.$$

These are bit-complexity bounds: operations on large integers are charged for their bit lengths. Polynomial space means the procedure avoids storing an exponentially large table, even though it performs a very large number of steps.

Consequences stated in the paper

Testing the count refutes ETH and its counting version. Since the theorem covers every fixed width, the manuscript also derives refutations of SETH and related gap and nondeterministic variants. A positive count can be converted into an actual satisfying assignment by fixing variables successively and checking which partial choice leaves solutions.

Other consequences have distinct guarantees. Conditional counts yield exactly uniform random satisfying assignments with polynomial expected overhead. A randomized approximation algorithm finds an assignment satisfying at least $\operatorname{OPT}(F)-\varepsilon m$ clauses, for any fixed $\varepsilon>0$, in subexponential time. Here $\operatorname{OPT}(F)$ is the largest satisfiable number of clauses; the approximation has exponentially small failure probability.

For a graph with $v$ vertices and $e$ edges, the paper gives deterministic algorithms counting independent sets and proper colorings with a fixed number of colors in $2^{o(v)}$ time. Its perfect-matching bound is $2^{o(v+e)}$, a different size parameter. An independent set contains no adjacent pair, a proper coloring gives adjacent vertices different colors, and a perfect matching pairs every vertex along selected edges.

The algorithm also gives a lower bound elsewhere. Corollary 1.4 states that some language $L$ in $\mathsf E^{\mathsf{NP}}$ has

$$C_L(n)>c\,n\sqrt{\log n}$$

for a constant $c>0$ and infinitely many input lengths. The class $\mathsf E^{\mathsf{NP}}$ allows deterministic $2^{O(n)}$ time with access to an oracle answering NP decision questions. The quantity $C_L(n)$ counts noninput gates in the smallest Boolean circuit for length-$n$ inputs, allowing gates with at most two inputs. This is a specific superlinear lower bound with explicit quantifiers.

5. Why the advance matters

Importance: 5/5. If correct, this result overturns one of the central quantitative assumptions in computational complexity. Improving an exponential base would strengthen an existing algorithmic tradition; making the exponent sublinear changes the type of running time that is possible.

Exact counting adds significance because it preserves much more information than a yes-or-no answer. Counts support sampling, optimization reductions, and combinatorial enumeration. Polynomial memory also avoids a common tradeoff in which faster search requires storing a huge collection of partial solutions.

The circuit consequence illustrates a productive connection established by Williams’s work on algorithms and lower bounds: an unexpectedly efficient search algorithm can imply that some other functions require large circuits. Thus an algorithmic upper bound can produce a complexity lower bound.

The consequences for conditional hardness need careful interpretation. A theorem saying “a faster algorithm would contradict ETH” remains a valid implication. If ETH is false, that implication no longer supplies the same reason to expect hardness. It does not itself construct the faster algorithm for the target problem.

6. The main idea

Turn logical conditions into algebra

For the clause $x_a\lor\neg x_b\lor x_c$, the polynomial

$$\Phi(x_a,x_b,x_c)=1-(1-x_a)x_b(1-x_c)$$

equals one exactly when the clause holds, on Boolean inputs. Multiplying these indicators over clauses and summing over all assignments gives the exact count. This identity is easy; evaluating the resulting sum efficiently is the challenge.

If clauses connected variables only within small independent groups, one could count each group separately and multiply. General formulas have clauses crossing groups. The manuscript introduces algebraic replacements that make those interactions depend on a small collection of shared linear measurements, such as weighted sums of bits in a group.

Once the measurements are fixed, each group can be summed independently. The algorithm enumerates possible measurement values and small-group assignments, then combines their contributions. The construction must keep both enumerations small enough to save time.

Recover a difficult value from easier evaluations

The replacements depend polynomially on a parameter $T$. At $T=0$ they restore the original variables, giving a polynomial $H$ with $H(0)=\#F$. At selected nonzero values of $T$, they admit the group decomposition.

The transformed expressions need not represent Boolean clauses at those other points. They are algebraic evaluations used to recover the original integer count. The paper constructs replacement forms of low degree through a matrix decomposition with few independent shared measurements and restricted nonzero entries.

Ordinary interpolation recovers a bounded-degree polynomial from enough values. Here the procedure also computes Taylor coefficients at its evaluation points. Hermite interpolation reconstructs a polynomial from this richer data. For instance, a quadratic is determined by its value and derivative at one point together with its value at a second point. The manuscript uses a much larger, carefully balanced version of this principle.

For arbitrary formulas, disjoint sparsification controls clause occurrences. Parity tests then encode whether an assignment violates selected clauses. The tests are constructed so that passing all of them is equivalent to satisfying the formula. Their deterministic construction uses exact counting for sparse polynomial systems, which is developed before it is used to solve SAT.

Sharpen the bound through tensor contraction

Appendix D obtains the stronger stated running times. A tensor here is a table with one Boolean index for each incident connection. Clause tables record satisfaction, and equality tables require different occurrences of a variable to agree. Multiplying table entries and summing over internal Boolean indices—contracting the network—counts satisfying assignments.

The proposed contraction algorithm recursively deforms connections to separate groups. It works with exact arithmetic modulo powers of two. Terms carrying sufficiently many factors of two vanish at the required precision, allowing the expansion to be truncated. Carefully chosen interpolation data and recursive group sizes control the work across all levels.

The arithmetic remains exact for the desired answer: since $0\le\#F\le2^n$, its residue modulo $2^{n+1}$ uniquely determines it. Processing branches and intermediate sums sequentially supplies the polynomial-space guarantee. The general-density case combines this contraction method with the sparse polynomial encoding.

7. Scope, limitations, and open questions

The width $k$ is fixed. Constants and polynomial exponents may depend on it; the theorem gives no comparable uniform guarantee when clause width grows with $n$. It is also an asymptotic result, with no practical crossover point established by the displayed bounds.

The claimed subexponential algorithm does not settle P versus NP. Nor do ordinary polynomial reductions transfer its running time unchanged: replacing an input of size $N$ by a formula with $N^3$ variables can consume a subexponential saving. Faster algorithms for other problems require reductions controlling the relevant size parameter.

Some hardness conjectures weaker than SETH, including the Orthogonal Vectors Conjecture discussed in the manuscript, might still hold. Refuting a sufficient assumption for them does not refute those conjectures themselves. Finding useful replacement assumptions and extracting further algorithms are separate research questions.

The repository’s formalization description reports deterministic exact counting and polynomial space with the weaker exponent

$$O_k\!\left(n(\log\log n)^2/\sqrt{\log n}\right).$$

It distinguishes that bound from the sharper manuscript bounds above. The release announcement also describes a planned independent examination led by Russell Impagliazzo, Ramamohan Paturi and Ryan Williams; it does not report a completed assessment.

8. Sources and further reading

The principal statements are Theorem 1.1 and Corollaries 1.2–1.4. Section 2 explains the interpolation method; Sections 3–6 develop exact counting and its SAT reduction; Appendix D gives the sharper bounds through tensor contraction. Section 1.1 discusses earlier algorithms and implications for fine-grained complexity.

The linked papers by Impagliazzo–Paturi and Impagliazzo–Paturi–Zane supply the historical formulation and sparsification framework. Schöning and Scheder illustrate the earlier progress on exponential rates; Williams explains the algorithms-to-lower-bounds connection.

Optional background: Boolean satisfiability, the Exponential Time Hypothesis, and Hermite interpolation.

Source manuscripts

• M1. OpenAI, The Exponential Time Hypothesis is False (October 25, 2026).

Sources consulted on 27 October 2026 at repository revision 7ef5c0c. Download the manuscript citations.