Concept
Clause-violation polynomials over the two-element field
For a positive literal x use the violation factor 1+x over F_2; it is one exactly when x is false. For a negative literal NOT x use factor x. Multiply the factors of a clause to obtain v_e: it is one exactly when all literals are false. For example, clause (x OR NOT y) has violation polynomial (1+x)y=y+xy. A width-at-most-k clause expands to at most 2^k monomials of degree at most k. Tautologies have zero violation polynomial; an empty clause has violation polynomial one. These are violation indicators, the complement of the earlier satisfaction indicators.
0
1
Updated 2026-11-07
Tags
Math