= Valiant's permanent reduction
{c}
<Valiant's permanent reduction> encodes <satisfying assignments> as weighted <cycle covers of a directed graph>. The <permanent of a matrix> sums the products of <edge weights> over these <cycle covers of a directed graph>.
<Variable gadget in Valiant's permanent reduction>[Variable tracks] enforce consistent <truth values>, <Clause gadget in Valiant's permanent reduction>[clause interchanges] enforce satisfaction, and signed <Exclusive-or gadget in Valiant's permanent reduction>[junctions] cancel invalid boundary choices. The original construction gives
$$
\operatorname{perm}(A_F)=4^{t(F)}\,\#\mathrm{SAT}(F),
$$
where $t(F)$ is twice the number of literal occurrences minus the number of clauses. <Arithmetic> recovers the predictable factor. The correspondence is between assignments and weighted groups of covers, rather than individual covers. Further transformations yield zero-one <matrices>.<The Complexity of Computing the Permanent by Leslie G. Valiant>[Lemma 3.1]{ref}
Back to article page
