= Solution
Interpret the <permanent of a matrix> as the total weight of the <cycle cover of a directed graph>[cycle covers] of its weighted directed graph. Valiant's reduction builds a graph from three constant-size components.
* A <Variable gadget in Valiant's permanent reduction> has exactly two relevant cycle-cover states, representing true and false, and exposes occurrence ports consistent with the selected state.
* A <Clause gadget in Valiant's permanent reduction> has external ports for its three literals and contributes a fixed total weight exactly when at least one selected literal satisfies the clause.
* An <Exclusive-or gadget in Valiant's permanent reduction> joins occurrence ports while allowing exactly one of two corresponding external edges. Its edges have weights in $\{-1,0,1\}$; unwanted cycle covers occur in sign-reversing pairs and cancel.
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.
Back to article page
