At a leaf no nonempty proper literal subset triggers branching. A fixed literal belongs to fewer than M^{c-1} width-c clauses for c>=2 and to at most one unit clause. Counting both polarities and widths gives at most B=2 sum_{j=0}^{k-1} M^j<=4M^{k-1} occurrences per variable. With the selected M, B=O_k([sigma^{-1}log(2/sigma)]^{k-1}). Every nonempty leaf clause uses at least one incidence, so its clause count is at most Bn. Repeated disjoint two-case partitions ensure each original satisfying assignment occurs in exactly one leaf. Original variables remain declared throughout, including unused ones.

Why sparsification leaves have bounded variable occurrences

Given rational 0<sigma<=1 and fixed k, test powers of two M>=G in increasing order. Compute C as above and h=ceil(log2(4CM)); accept the first M satisfying G h<=sigma M by exact cross-multiplication. Then the tree bound is at most (Cn+1)^2 2^{sigma n}. Since C=O_k(M^{k-2}), the first successful M is O_k(sigma^{-1}log(2/sigma)). If the supplied numerator and denominator of sigma have total encoding length L, parameter search uses polynomial time in L for fixed k. This bit-cost statement concerns parameter construction, not generation of all tree nodes.

AI Agents

Set C=4 sum_{j=0}^{k-2}(3M)^j, G=4 sum_{j=0}^{k-2}3^j, D=Cn and r=Gn/M. For M>=G, insertion bounds give depth at most D and at most floor(r) B choices. Deterministic branching identifies a node by its depth and B positions: at most (D+1) sum_{a=0}^{floor(r)} binom(D,a) descriptions. The factorial bound a!>=(a/e)^a gives binom(D,a)<=(eD/a)^a<=(eD/r)^r for 1<=a<=r<=D, because (eD/a)^a increases up to D. There are at most D+1 terms, including a=0. Since eD/r=eCM/G<=4CM, the tree has at most (Cn+1)^2 2^{(Gn/M)log2(4CM)} nodes. If r<1 no B choices are possible: at most D+1 nodes suffice.

Encoding sparsification paths by their few expensive branches

OpenAI. The Exponential Time Hypothesis is False. Manuscript dated October 17, 2026, revised October 25, 2026. This reference pins commit 42907c9e999cc00d6abe7a50bfc1023250edd1b9. The introduction defines the exact-counting task used by this learning path; citing it does not establish that its main theorem is correct.

https://github.com/openai/math/blob/42907c9e999cc00d6abe7a50bfc1023250edd1b9/preprints/The-Exponential-Time-Hypothesis-is-False-October-25-2026/paper.pdf

Learn Before

Learn After

Learn After