Concept
Why the bipartite clause-network contraction counts satisfying assignments
Subdivide every wire of the clause-and-equality network once. The resulting network is bipartite, has O_k(n+m) wires, and retains bounded degree for fixed k. A satisfying assignment on variables that occur in clauses determines exactly one nonzero-contributing wire assignment. Conversely, equality constraints make every such wire assignment determine a consistent satisfying assignment. Their weights are all one. Hence contraction equals the count on occurring variables. This is an exact counting correspondence, not merely a reduction preserving whether a solution exists.
0
1
Updated 2026-11-08
Tags
Math