Concept
Testing clause violations by sparse parity equations
For indexed clauses e=1,...,m form the violation vector v(x). A binary row a specifies the equation sum_e a_e v_e(x)=0 over F_2. For a matrix A, let N(A) count assignments passing all its equations. Every satisfying assignment has v(x)=0 and passes every row; a nonsatisfying assignment can also pass because violations cancel in parity. Thus N(A)=#F+D(A), where D(A) is the number of false positives, not known to the algorithm. With formula (x) AND (y), the single row testing both clauses lets (0,0) pass. Sparse tests alone are not an exact reduction until all false positives are excluded.
0
1
Updated 2026-11-07
Tags
Math