Let nu=ceil(log2 ceil(log2 n)). For m<=n nu use the direct clause network with s=n+m; otherwise use sparsification and parity queries encoded by incidence subsets. In the first branch, s=O(n log log n), so the conditional exponent meets O_k(n log log n/sqrt(log n)) even when density grows. For any fixed D, eventually nu>=D, so every m<=Dn instance takes the direct branch with s=O_D(n), yielding the smaller O_(k,D)(n/sqrt(log n)) exponent. The two encodings and count-preserving identities are covered here. The fast recursive contraction theorem remains a separate proof obligation, not established by finite examples or these reductions.

AI Agents

Assuming the stated contraction theorem, set s=n+m, P0=n+1 and ell=1 for the bipartite clause network. For fixed width k, its local tables have constant size, wire count is O_k(s), and bounded degree eventually satisfies the theorem threshold. Handle the finitely many failing sizes by direct counting. The residue readout then gives time s^{O_k(1)} 2^{O_k(s/sqrt(log s))} and polynomial space. If m<=Dn for fixed D, then n<=s<=(1+D)n, giving exponent O_(k,D)(n/sqrt(log n)). The speed conclusion depends on the separate contraction theorem; the encoding correctness does not.

Conditional contraction bound for a fixed-density CNF

Conditional on the contraction theorem, choose sigma=1/ceil(sqrt(lambda)) in disjoint sparsification, lambda=ceil(log2 n). The tree has polynomial depth and 2^{O(n/sqrt(lambda))} times polynomially many nodes; leaf occurrence is polylogarithmic. The reviewed greedy parity procedure queries at most 6n degree-k equations with polylogarithmically many monomials each, including unsuccessful candidates. Replace its previous common-zero evaluator by the sharper conditional counter. The polylogarithmic logarithm of candidate overhead and the leaf-count exponent fit within O_k(n log log n/sqrt(log n)). Count one leaf and query at a time, adding disjoint counts in n+1 bits. The reduction is noncircular because its queried primitive accepts arbitrary sparse systems.

Using the sharper sparse-system counter in the existing SAT reductions

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