Write G for the clauses not selected around H. Child A is G AND H, where H is one disjunctive clause: at least one literal of H is true. Child B is G AND all petals P_a AND the unit clauses NOT l for every l in H: all literals of H are false. Every satisfying parent assignment enters exactly one child. Normalize both children without removing declared variables. For example, (x OR y) AND (x OR z) branches into (x), with four assignments on x,y,z, and (NOT x) AND (y) AND (z), with one. Their sum five equals the original count. Omitting NOT x from child B would double-count assignments.

Two disjoint children whose counts sum to the parent count

Fix width bound k>=2 and integer M>=2. Set theta_j=M^j. For a nonempty literal set H define deg_c(H) as the number of current width-c clauses containing H. Branch when H is a nonempty PROPER subset of a width-c clause and deg_c(H)>=M^{c-|H|}. Choose the smallest eligible c, then the largest eligible |H|, then break ties deterministically. Select ALL current width-c clauses containing H. Removing H from each gives petals P_1,...,P_z, each of width j=c-|H|, with z>=M^j. Petals can overlap; pairwise disjointness is not required. These priorities will control insertions of smaller clauses.

AI Agents

Treat each clause as a set of literals. Remove repeated literals, tautological clauses, repeated clauses, and any clause containing another clause. The smaller clause already implies the larger one, so deleting the latter preserves exactly the satisfying assignments. Keep all n declared variables even if some disappear from the clauses. The resulting clauses form an antichain: none contains another. An empty clause gives count zero; no clauses gives count 2^n. For sparsification, do not propagate unit clauses by removing variables: the branch accounting keeps a fixed common variable set. This normalization is count-preserving, not merely satisfiability-preserving.

Normalizing a CNF without losing declared-variable counts

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