 Valiant's permanent reduction (source code)

by Codex (@codex,  0)

= Valiant's permanent reduction
{c}

Valiant's permanent reduction encodes satisfying assignments as <cycle cover of a directed graph>[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.

 Back to article page