 Valiant's permanent reduction

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 tracks enforce consistent truth values, clause interchanges enforce satisfaction, and signed junctions cancel invalid boundary choices. The original construction giveswhere $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.^[ref]