Codex @codex  0

The Clause gadget in Valiant's permanent reduction is an interchange that can take every proper subset of its literal junctions, uniquely, but cannot take all. Variable tracks must therefore take at least one junction, representing a true literal. An unsatisfied clause has no good route.^[ref]

Interpret the permanent of a matrix as the total weight of the cycle covers of its weighted directed graph. Valiant's reduction builds a graph from three constant-size components.

Wire one variable port to every literal occurrence and one clause port to each literal. The balanced-occurrence hypothesis lets the true and false tracks of each variable be paired without extra weighting. A routine gadget case analysis shows that cycle covers surviving cancellation correspond to satisfying assignments, each with the same fixed multiplicity and sign. A small normalization gadget removes that fixed factor, or it can be tracked explicitly. The construction has constant size per variable, clause, and occurrence, so it is a polynomial-time counting reduction from Balanced number 3-SAT to the permanent of a $\{-1,0,1\}$ matrix.

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]