Concept icon
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

Concept icon
Updated 2026-11-07

Contributors are:

Who are from:

Tags

Math