Past exam of the mathematics course of the University of Cambridge / 2023 / iii / Paper 124 / 4

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.

View $M$ as a directed graph with nonnegative integer edge weights. For an edge of weightbuild a binary path-counting gadget with one entrance and one exit and exactly $w$ entrance-to-exit routes. Starting with one route, a constant-size diamond doubles the number of routes; processing the bits from most significant to least significant repeatedly doubles and, when $b_j=1$, adds one bypass route. The gadget has $O(n)$ vertices and only zero-one edges.

Add forced internal edges and self-loops so that a cycle cover not using the simulated edge extends uniquely across the gadget, whereas a cycle cover using it has exactly one extension for each entrance-to-exit route. Replacing every weighted edge therefore multiplies each original cycle cover by precisely the product of its selected edge weights. Summing over covers givesThere are $n^2$ entries and each gadget has $O(n)$ size, so $N$ is constructed in polynomial time.