Motivation
A reduction for a decision problem only has to preserve whether a solution exists. A counting reduction must be more careful: introducing auxiliary choices can turn one solution into several and change the answer. A parsimonious reduction preserves the exact count. We will build one from Boolean circuits to three-literal clauses and use it to see how counting differs from ordinary satisfiability. We then study the permanent, where a sum over permutations counts perfect matchings in a bipartite graph.
For a Boolean formula with a declared list of variables, is the number of assignments to that list making the formula true. Unused declared variables still contribute choices. In this unit a 3-CNF formula has clauses of at most three literals; if exactly three occurrences per clause are required, repeating a literal pads any nonempty shorter clause without changing the set of satisfying assignments. Variables introduced by a reduction are included in the output list and therefore contribute to its count unless the clauses force them uniquely.
A parsimonious reduction from a counting function to is a polynomial-time computable mapping with for every input. This is stronger than preserving whether the value is zero. Other counting reductions, including oracle reductions, have different definitions; a completeness result must say which kind it uses. For example, the transformation that adds one unconstrained Boolean variable changes a count to . Dividing the returned count by two recovers , but the raw map is not parsimonious. This distinction becomes more consequential when a gadget creates different numbers of extensions for different input assignments: a single fixed division factor may then fail.
Why a decision gadget may change a count
Counterexample mode
Auxiliary variables can change the count
Suppose one claims that any transformation preserving satisfiability also preserves the number of satisfying assignments. Take the formula on the declared variable list . It has exactly one satisfying assignment. The formula on the list is satisfiable exactly when is, but it has two satisfying assignments: with , and with . The added variable is unconstrained. The transformation preserves existence but is not parsimonious; the repair is to require that every input solution have exactly one extension.
Common mistake
(Equisatisfiable does not mean equally many)
A proof that every input solution has at least one output extension and every output solution projects to an input solution establishes satisfiability equivalence. Exact count preservation additionally requires that each input solution have exactly one output extension, or some other explicit count-preserving bijection. Simply introducing auxiliary variables and checking the yes/no direction does not establish that property.
Encoding one Boolean gate
Suppose a circuit has a topological order of AND, OR, NOT and constant gates, with two inputs for each AND/OR gate and one for each NOT gate. Introduce one fresh variable for each gate's output. For a gate impose
If , the first two clauses force . If , the third clause forces . Hence the clauses hold exactly when , and the allowed is unique once are fixed.
The same analysis covers OR and NOT gates. For and impose respectively
In the OR case, or forces by the first two clauses, and forces by the third. In the NOT case, forces and forces . In each case the clauses hold exactly when equals the gate operation applied to its inputs, and is uniquely determined by them. A constant-one gate receives a unit clause and a constant-zero gate receives a unit clause ; in either case its output is uniquely forced. Gates may share predecessors; each gate still receives its own output variable. The counting argument below adds the global bijection between input assignments and auxiliary-variable assignments.
Worked example 5.3.1
(Checking an AND gate in both directions)
If , the clause forces , and with all three clauses hold. If , the clause forces , which again satisfies the other clauses. The remaining two input pairs are analogous. For every fixed pair there is exactly one legal , equal to .
Theorem 5.3.2
(A parsimonious circuit-to-3-CNF reduction)
There is a polynomial-time mapping from a Boolean circuit with a declared list of input variables to a 3-CNF formula such that the number of satisfying assignments of on all its declared variables equals the number of input assignments accepted by .
Proof
(Proof)
Create a fresh variable for every gate and include the appropriate gate-equivalence clauses. Add a unit clause forcing the output gate's variable to be one. If the output is directly an input, use its unit clause. If it is directly a constant, add one fresh variable and force for constant one, or impose both and for constant zero. These two cases preserve respectively every input assignment exactly once and no input assignment. The number of new variables and clauses is linear in the circuit description. Repeating a literal pads short nonempty clauses to exactly three occurrences if that convention is required; it introduces no new variable or satisfying assignment.
Fix any assignment to the declared input variables. Evaluate the circuit in topological order and assign each new variable the actual value of its gate. All gate clauses hold. Conversely, in any satisfying assignment, each gate's clauses force its new variable to equal the gate operation applied to predecessor values. Induction in topological order shows that every gate variable equals the value obtained by evaluating . Thus the fixed input assignment has exactly one extension satisfying all gate clauses. The output clause accepts that extension precisely when outputs one. Projection to the input variables is therefore a bijection from satisfying assignments of to accepting input assignments of , proving equality of counts.
Proof X-ray
Why uniqueness, and not only existence, of the extension
The reduction needs two facts about the gate variables, and they do different jobs. Existence of an extension, obtained by evaluating the circuit in topological order, shows that every accepted input survives. Uniqueness, obtained by induction in topological order because each gate's clauses force its variable once its predecessors are fixed, shows that it survives exactly once. Satisfiability equivalence needs only existence; parsimony needs both. The unit clause on the output gate then selects, among the inputs, exactly those whose unique extension has output one. Without that clause, every input assignment would still have exactly one extension, and the formula would have satisfying assignments on input variables, whatever the circuit computes.
The proof also handles an unused input variable: its value remains a free input choice on both sides of the bijection. The construction is often called a gate encoding, but the crucial property here is uniqueness of the auxiliary values, which must be checked rather than inferred from a name.
Worked example 5.3.3
(Counting a small encoded circuit)
Let and introduce one gate variable . Add the three OR-equivalence clauses and the unit clause . The accepted input assignments are , and . For each, the gate clauses force ; the assignment forces and fails the unit clause. Hence the output formula has exactly three satisfying assignments on , not six.
If one starts with a witness verifier, standard uniform simulation of a polynomial-time deterministic computation by a polynomial-size circuit gives a circuit whose input bits are the witness and whose hardwired input is . Composing that simulation with the theorem gives a parsimonious reduction to . We use the machine-to-circuit simulation as an explicitly unproved background theorem here. The gate encoding itself is proved above; it should not be mistaken for a proof of that simulation.
The permanent and perfect matchings
For an matrix , define its permanent by
This resembles a determinant but does not attach a sign to odd permutations. For a – matrix, regard row and column as vertices on opposite sides of a bipartite graph, with edge exactly when .
Proposition 5.3.4
(A 0–1 permanent counts perfect matchings)
For a – matrix , is the number of perfect matchings in its associated bipartite graph. The function mapping to this permanent belongs to .
Proof
(Proof)
A permutation chooses exactly one column for each row and uses every column once. The product equals one exactly when all selected pairs are edges; then those pairs form a perfect matching. Conversely every perfect matching selects a unique column in each row and hence a unique permutation. All other products are zero, so the sum counts matchings.
To express the count as a witness function, encode a proposed sequence of column indices in fixed-width binary blocks. A polynomial-time verifier rejects out-of-range or repeated indices and checks that every proposed edge occurs. Every perfect matching has exactly one such valid sequence, while invalid encodings are rejected. Thus the number of accepting witness strings is the permanent. The case can use one bit per index, and finite exceptional sizes can be handled explicitly.
Worked example 5.3.5
(A 3-by-3 permanent)
For
choose the column used by the first row. If it uses column , the remaining submatrix is all ones and contributes two matchings. If it uses column , row must use column and row then uses column , contributing one. Column is unavailable to row . Therefore . The argument counts matchings, not signed terms; the determinant may differ.
Parity is easier to extract than the exact count
Over the field , . The determinant expansion is
Reducing entries and the integer determinant modulo two makes every sign equal to one, so . Gaussian elimination over computes the determinant in polynomial time. Thus one can decide whether the number of perfect matchings in a bipartite graph is odd without computing that number exactly by this method.
Proposition 5.3.6
(Permanent parity for 0–1 matrices)
The parity of for a – matrix is computable in deterministic polynomial time.
Proof
(Proof)
Reduce to a matrix over . Term by term in the permutation expansions, the determinant and permanent agree in that field because each permutation sign is . Elementary row operations compute the determinant using polynomially many field operations; swapping rows changes the usual sign, which is also in . The result is the permanent reduced modulo two. It equals one exactly when the integer count is odd.
Worked example 5.3.7
(Parity can vanish despite existing matchings)
For the all-ones matrix there are two perfect matchings, one for each permutation. Its permanent is , so its parity is zero. The determinant modulo two is also zero because its two rows are equal. Thus an even parity answer does not mean that no matching exists; it only says the exact count is even.
The famous result that exact computation of the – permanent is -complete under an appropriate counting reduction is Valiant's theorem. It is not proved here. The polynomial-time parity calculation does not prove that exact permanent computation is easy, and membership in alone does not prove hardness. Likewise, Toda's theorem requires additional oracle and reduction machinery beyond the constructions in this unit.
A counting problem with a polynomial-time recurrence
Not every counting problem is difficult in the same sense. In a finite directed acyclic graph, the number of directed paths from a vertex to a designated target can be computed by dynamic programming. Set for the empty path from to itself. Process the other vertices in reverse topological order and set
Every path from begins with exactly one outgoing edge, so the sets counted by the summands are disjoint. Vertices with no path to receive zero. The value at the source is the desired count.
Worked example 5.3.8
(Counting directed paths without listing them)
Let the edges be . Starting at the target gives and . Then , , and . The three paths are , and . The recurrence groups them by their first edge and counts each exactly once.
For a simple acyclic graph with vertices, a path visits each vertex at most once. A crude upper bound of possible vertex sequences has only bits, so all counts in the recurrence have polynomial bit length. Polynomially many additions therefore give a polynomial-time exact algorithm. The acyclicity assumption is essential to this simple recurrence: a directed cycle can produce infinitely many walks, and even when only simple paths are counted the recurrence would have to remember which vertices are already used. This example also shows that membership in alone says nothing about whether a particular count is hard.
Practice and solutions
Quick check
(Why does adding an unconstrained fresh Boolean variable generally double a satisfying-assignment count?)
Ask how many values the new variable may take.
Solution · Answer
Each original satisfying assignment extends in exactly two ways, with the new variable equal to zero or one. No new clause restricts it.
Quick check
(If and , what value of satisfies the AND-gate equivalence clauses?)
Look at the clause that contains .
Solution · Answer
The clause forces . With , all three AND-equivalence clauses hold.
Quick check
(Why does the circuit-to-CNF proof give exactly one extension for each input assignment?)
Think of the gates in topological order.
Solution · Answer
The clauses for each gate enforce the gate's output as a function of its already determined predecessors. Induction through a topological order determines every auxiliary variable uniquely.
Quick check
(Compute the permanent of .)
Sum over the two permutations of .
Solution · Answer
There are two permutations and both contribute one, so the permanent is .
Quick check
(If the permanent of a – matrix is odd, what is its determinant over ?)
Compare the two expansions modulo two.
Solution · Answer
It is one: the determinant and permanent agree modulo two.
Quick check
(Does a zero determinant over prove the bipartite graph has no perfect matching?)
Try the all-ones matrix.
Solution · Answer
No. It proves only that the number of matchings is even. The all-ones matrix has two matchings and determinant zero over .