Definition
A counting polynomial that restores the count at zero
After the parameterized replacements, multiply the transformed clause values for each original Boolean assignment and sum the products over all assignments. Finite sums and products of polynomials remain polynomials, so this defines H(T). At T=0 every replacement restores its original input, giving H(0)=#F. Other values may be weighted sums, not satisfying-assignment counts. For the one-clause formula p over one declared variable, replace x by (1+T)x. Then H(T)=(1+T)0+(1+T)1=1+T: H(0)=1 but H(2)=3. Boolean-only identities need not survive replacement: u*u=u for u=0 or 1, but not for u=2. Recovering H(0) remains a separate task.
0
1
Updated 2026-11-07
Tags
Math