Valiant's permanent reduction encodes satisfying assignments as cycle covers so that their weighted sum is the permanent of a matrix. Local gadgets enforce variable consistency and clause satisfaction, while signed contributions cancel invalid covers.
The variable gadget has two relevant cycle-cover states, representing the two truth values, and exposes ports that transmit the chosen value to occurrences of the variable.
The clause gadget contributes the required fixed weight precisely when at least one incident literal port represents a satisfying value.
The exclusive-or gadget connects two ports while allowing exactly one corresponding external edge to participate. Signed edge weights pair and cancel unwanted cycle covers.
A binary path-counting gadget replaces an edge of nonnegative integer weight by a zero-one directed graph with exactly routes from its entrance to its exit. Repeated doubling and conditional addition follow the binary expansion of using only linearly many vertices in its bit length.
Articles by others on the same topic
There are currently no matching articles.