Why can counting perfect matchings be harder than finding one?
A perfect matching pairs every vertex with exactly one partner. In a bipartite graph with left vertices $L_1,\ldots,L_n$ and right vertices $R_1,\ldots,R_n$, a perfect matching is a permutation $\pi$ satisfying $L_iR_{\pi(i)}\in E$ for every $i$. A search algorithm needs one such permutation. A counting algorithm must account for all of them, including alternatives a successful search can ignore.
Consider the adjacency matrix
$$A=\begin{pmatrix}1&1&0\\ 1&1&1\\ 0&1&1\end{pmatrix}.$$
The identity assignment works immediately, but it is only one of three perfect matchings. Counting them means evaluating the permanent,
$$\operatorname{per}(A)=\sum_{\pi\in S_n}\prod_{i=1}^n A_{i,\pi(i)}.$$
For a zero-one matrix each product is the indicator of an admissible matching. Finding a bipartite perfect matching is polynomial-time solvable, whereas exact zero-one permanent computation is an established $\#\mathrm P$-complete problem under polynomial-time counting oracle reductions. The theorem classifies computational difficulty; it does not constitute an unconditional proof that no polynomial-time exact algorithm exists. Precise reductions and input restrictions matter.
A count is also not the same task as listing every solution. The complete bipartite graph has $n!$ perfect matchings, whose count has only $O(n\log n)$ binary digits, while an explicit list contains exponentially many records. Efficient counting can coexist with an unavoidable output cost for exhaustive enumeration.
This chapter's foundation is the permutation encoding, the six-permutation calculation below, and one further proof principle: a reduction preserves a count only if the target solutions have a controlled correspondence to the source solutions. A bijection preserves the count. A unique auxiliary-variable extension gives a bijection by projection. An unrestricted extra Boolean variable doubles the count. These elementary observations suffice for the core investigation without the optional numbered extensions.
Review matchings and representatives, algebraic enumeration, combinatorial algorithms, and approximate counting for earlier techniques.
Why can counting perfect matchings be harder than finding one?
For the displayed matrix, list $\pi(1)\pi(2)\pi(3)$ and check its three matrix entries:
| Permutation | Product | Reason |
|---|---|---|
| $123$ | $1$ | All three diagonal entries exist |
| $132$ | $1$ | Entries $11,23,32$ exist |
| $213$ | $1$ | Entries $12,21,33$ exist |
| $231$ | $0$ | Entry $31$ is absent |
| $312$ | $0$ | Entry $13$ is absent |
| $321$ | $0$ | Entry $13$ is absent |
Thus the count is three. An augmenting-path search may return $123$ without examining all other permutations. This instance demonstrates the difference between tasks, not a lower bound on every possible algorithm.
Question to revisit. If a transformation replaces each matching by two target solutions, has it proved count equality? Solution: no. It proves a factor-two relation only after establishing that every source solution has exactly two preimages and that no other target solutions occur. A decision-equivalence argument alone establishes neither fact.
48.1 Counting complexity classes
Optional extension; not required to complete the chapter foundation.
A function $f:\{0,1\}^{\ast}\to\mathbb N$ belongs to $\#\mathrm P$ if there is a polynomial-time predicate $R(x,y)$ and a polynomial $p$ such that
$$f(x)=\lvert\{y\in\{0,1\}^{p(\lvert x\rvert)}:R(x,y)=1\}\rvert.$$
Equivalently, it counts accepting branches of a polynomial-time nondeterministic machine with a fixed witness convention. The class is a class of functions, whereas $\mathrm{NP}$ is a class of decision languages. The associated existence question asks whether $f(x)\gt0$.
The class $\mathrm{FP}$ contains functions computed deterministically in polynomial time, with their outputs written in binary. A $\#\mathrm P$ count has at most polynomially many output bits, even if its numerical value is exponential. $\mathrm{GapP}$ permits a difference of two $\#\mathrm P$ functions and can therefore take negative values. These definitions and hardness phenomena originate in Valiant's counting-complexity work.
Solved example. To place bipartite perfect-matchings counting in $\#\mathrm P$, encode a permutation canonically by its list of values. Verify that each value is in $[n]$, that the values are distinct, and that every selected matrix entry is one. Reject malformed encodings and require any padding bits to be zero. Each matching then has exactly one accepted witness. Counting arbitrary ordered edge lists without removing order redundancy would instead count $n!$ encodings per matching.
For $\#\mathrm{SAT}$, the instance includes its declared variable set, and the witnesses are full assignments to that set. A declared variable absent from the formula still contributes a factor of two. This convention prevents silent changes of the sample space during simplification.
Complexity classifications count accepted witnesses under a specified encoding. Before asserting membership, completeness, or count preservation, check that one mathematical solution corresponds to the intended number of witnesses.
Exercise. Count assignments satisfying $x\lor y$ when the declared variable set is first $\{x,y\}$ and then $\{x,y,z\}$. Hint: $z$ is unrestricted. Solution: the counts are three and six. The decision answer is yes in both cases, but the counting functions differ.
48.2 #P-completeness
Optional extension; not required to complete the chapter foundation.
A parsimonious reduction from $f$ to $g$ is a polynomial-time instance map $T$ satisfying $f(x)=g(T(x))$. A polynomial-time counting Turing reduction may instead query several instances of $g$ and combine their answers. A metric reduction allows a polynomial-time transformation of both the instance and the returned value. A completeness statement must specify which reduction it uses.
$\#\mathrm{SAT}$ and counting satisfying inputs of Boolean circuits are established $\#\mathrm P$-complete problems; a verifier circuit gives the witness-count encoding, and a count-preserving gate encoding converts circuits into formulas. Proof scope: the general polynomial circuit simulation of a verifier is omitted, while the unique-extension gadget needed for the conversion is proved below. Primary counting foundations are in Valiant.
For an OR gate $u=x\lor y$, the three clauses
$$ (\neg x\lor u)\land(\neg y\lor u)\land(x\lor y\lor\neg u)$$
force exactly the desired value of $u$. For an AND gate $w=u\land v$, use
$$(\neg w\lor u)\land(\neg w\lor v)\land(\neg u\lor\neg v\lor w).$$
For a NOT gate $v=\neg x$, use $(x\lor v)\land(\neg x\lor\neg v)$. Given the inputs of an acyclic circuit, topological gate order determines every auxiliary output uniquely. Assert its final output with a unit clause. Every satisfying input therefore has exactly one satisfying extension, and every target model projects to a satisfying input. This proves parsimoniousness of the circuit-to-at-most-three-literal-CNF transformation. It does not require clauses to contain exactly three distinct literals.
#P-completeness: a worked example
Take a circuit with inputs $x,y$, one OR output $u=x\lor y$, and require $u=1$. Add the three OR clauses and the unit clause $(u)$.
| Input $xy$ | Forced $u$ | Satisfies output assertion? | Target extensions |
|---|---|---|---|
| $00$ | $0$ | No | $0$ |
| $01$ | $1$ | Yes | $1$ |
| $10$ | $1$ | Yes | $1$ |
| $11$ | $1$ | Yes | $1$ |
The source and target counts are both three. If only implications $x\Rightarrow u$ and $y\Rightarrow u$ were retained, input $00$ would allow $u=1$, creating a false target model. The reverse implication encoded by the third clause is essential. This checks the gadget's multiplicity, rather than claiming that one small example proves the whole completeness theorem.
Exercise. What happens if the correct target formula is conjoined with $(z\lor\neg z)$ for a fresh declared variable $z$? Hint: projection now has two preimages. Solution: every target model doubles. One can recover the original count by dividing by two, but the transformation is no longer parsimonious.
48.3 Complexity of perfect-matchings counting
Optional extension; not required to complete the chapter foundation.
The permanent identity is a bijection between permutations with nonzero products and perfect matchings of a bipartite graph. It gives $\#\mathrm P$ membership for zero-one matrices. The established theorem of Valiant90044-6) makes exact zero-one permanent computation $\#\mathrm P$-complete under polynomial-time counting Turing reductions. Omitted prerequisite: the signed/weighted gadget and interpolation machinery of the hardness proof. This is not asserted to be a parsimonious reduction from arbitrary satisfiability instances: if such an efficiently produced zero-one permanent instance preserved zero exactly, a matching-existence algorithm would decide satisfiability in polynomial time.
Exact exponential algorithms remain useful. For an $n\times n$ matrix, let $D(S)$ count assignments of the first $\lvert S\rvert$ rows to the distinct columns in $S$. Then
$$D(\varnothing)=1,\qquad D(S)=\sum_{j\in S}A_{\lvert S\rvert,j}D(S\setminus\{j\}).$$
This computes the permanent in $O(n2^n)$ arithmetic operations and $O(2^n)$ table entries. For binary inputs the integers have $O(n\log n)$ bits; bit complexity must account for arithmetic on those integers. It is exponential in $n$, not polynomial merely because each table update is simple.
Solved example. The foundation's matrix has three matchings. The SVG displays its seven admissible graph edges in each panel and highlights one complete matching at a time. Every highlighted set uses each left and right vertex exactly once; no absent entry is drawn. The three panels exhaust the successful permutations from the motivating table.
Planarity changes the exact problem: weighted perfect matchings of planar graphs can be counted in polynomial time via a Pfaffian orientation. This is an established restricted algorithm, not a contradiction to general $\#\mathrm P$-completeness. The algebraic mechanism is introduced in section 48.9.
Exercise. Evaluate the first two layers of $D$ for the displayed matrix. Hint: row one uses columns one or two. Solution: $D(\{1\})=1$, $D(\{2\})=1$, $D(\{3\})=0$. Then $D(\{1,2\})=2$, $D(\{1,3\})=1$, $D(\{2,3\})=1$. The final row gives $D(\{1,2,3\})=0\cdot1+1\cdot1+1\cdot2=3$.
48.4 The permanent versus determinant
Optional extension; not required to complete the chapter foundation.
For a square matrix over a field,
$$\det A=\sum_{\pi\in S_n}\operatorname{sgn}(\pi)\prod_iA_{i,\pi(i)}.$$
The determinant includes permutation signs; the permanent does not. Cancellation supports Gaussian elimination and other polynomial-time determinant algorithms. A polynomial-time algorithm for one signed sum is not automatically an algorithm for the unsigned sum.
Solved example. For the foundation matrix, the valid permutations are $123,132,213$. Their determinant signs are $+1,-1,-1$, so $\det A=-1$, while $\operatorname{per}A=3$. For the all-ones two-by-two matrix, the determinant is zero and the permanent is two. A zero determinant therefore does not certify absence of a perfect matching.
Over characteristic two the signs coincide, so the permanent equals the determinant in that field. This computes the parity of an integer matching count for zero-one inputs, not its full nonnegative integer value. The three-matchings example has permanent and determinant both one modulo two. Modular information and exact output must be distinguished.
Valiant's permanent hardness theorem is an established Boolean/bit-model result. Algebraic circuit questions compare polynomial families over specified fields and use a different complexity model; a symbolic determinant representation or an arithmetic-circuit lower bound must state its dimensions, allowed coefficients, and uniformity. This chapter uses no unproved separation between the exact-count classes and does not treat cancellation intuition as a general lower-bound proof. Primary source for the permanent result: Valiant90044-6).
Exercise. If a count is six, what information does a determinant calculation modulo two recover in a setting where permanent equals determinant? Hint: reduce the output. Solution: zero, meaning an even number of solutions. It does not distinguish zero from six or any other positive even count.
48.5 Approximate counting algorithms
Optional extension; not required to complete the chapter foundation.
A fully polynomial randomized approximation scheme, or FPRAS, for a nonnegative count $Z(x)$ returns $\widehat Z$ satisfying
$$\Pr\bigl((1-\varepsilon)Z\le\widehat Z\le(1+\varepsilon)Z\bigr)\ge1-\delta$$
in time polynomial in the input length, $1/\varepsilon$, and $\log(1/\delta)$, for $0\lt\varepsilon,\delta\lt1$. The fixed-success-probability definition is equivalent after amplification. When $Z=0$, multiplicative accuracy requires zero output on the success event; additive error is a different guarantee.
The established Jerrum–Sinclair–Vigoda theorem supplies an FPRAS for the permanent of a matrix with nonnegative rational entries, with input bit lengths included. For zero-one matrices, zero can be detected by finding a perfect matching. Proof sketch and omitted prerequisites: the algorithm samples from carefully weighted perfect and near-perfect matching states, uses a rapidly mixing chain, and estimates ratios along an annealing schedule. The mixing proof and weight-adjustment analysis are omitted. An arbitrary local matching chain does not inherit the theorem's guarantee.
Solved example: a simple estimator with a limited scope. For a zero-one matrix, sample a uniform permutation and let $B$ indicate that it is a valid matching. Then $X=n!B$ has expectation $Z=\operatorname{per}A$ and variance $n!Z-Z^2$. With $M$ independent samples, the relative variance of the mean is $(n!/Z-1)/M$ when $Z\gt0$.
For the foundation matrix $n!=6,Z=3$, the relative variance is $1/M$. Chebyshev gives relative error at most $1/4$ with failure probability at most $1/4$ once $M\ge64$. This is a complete small-instance guarantee. For the identity matrix, however, $Z=1$ and the factor is $n!-1$, so the same approach is not an FPRAS on arbitrary input. Unbiasedness by itself does not imply efficient relative approximation.
Exercise. What is the probability a uniform permutation gives a valid matching for the $n\times n$ identity matrix? Hint: only one permutation works. Solution: $1/n!$. Seeing no success in a moderate sample cannot reliably distinguish this positive count from zero, so support/existence information matters.
48.6 Randomized reductions in counting complexity
Optional extension; not required to complete the chapter foundation.
An approximation-preserving reduction is a randomized oracle algorithm that converts an approximation scheme for one problem into an approximation scheme for another. It controls running time, requested relative errors, oracle failure probabilities, and zero cases. An exact counting Turing reduction need not preserve efficient approximation: subtraction of nearly equal large quantities can magnify relative error. The established formal framework is Dyer, Goldberg, Greenhill, and Jerrum.
Solved example: random hashing with an audited variance. Let $S\subseteq\{0,1\}^n$ be a solution set of size $Z$. Choose a uniform affine map $h(x)=Ax+b$ to $\mathbb F_2^r$, with every matrix and offset bit independently uniform. Let $Z_h$ count solutions in the bucket $h(x)=0$. Every input hits it with probability $2^{-r}$; indicators for distinct inputs are independent because the affine family has uniform pair marginals. Hence
$$\mathbb E[2^rZ_h]=Z,\qquad\operatorname{Var}(2^rZ_h)=Z(2^r-1).$$
This is a proved estimator identity. It assumes the bucket can be counted or otherwise suitably estimated; adding a random constraint does not solve that subproblem for free. If $2^r\gg Z$, relative variance is large. A full hashing-based reduction must choose a scale and specify its oracle, rather than simply claim the bucket is “small.”
The four source assignments in the final investigation have $Z=4$. For $r=1$, exact enumeration of all affine hash seeds gives mean four and variance four for $2Z_h$. The example verifies expectation and multiplicity under randomized restrictions, not an exact parsimonious reduction.
For a contrasting exact reduction, if $g(T(x))=2^{k(x)}f(x)$ with known polynomially bounded $k(x)$ and no extra target solutions, division by the factor preserves relative approximation error. By contrast, recovering $f$ as $g_1-g_2$ may fail: approximating $10^6+1$ and $10^6$ within one percent does not determine their difference one accurately.
Exercise. If each of $q$ oracle calls fails with probability at most $\delta/q$, bound the chance any call fails. Hint: independence is unnecessary. Solution: the union bound gives at most $\delta$. Error budgets must also control how errors propagate through the arithmetic, not only how often the oracle fails.
48.7 Parameterized counting complexity
Optional extension; not required to complete the chapter foundation.
A parameterized count has input $(x,k)$. Fixed-parameter tractability asks for time $f(k)\lvert x\rvert^c$ with a constant $c$ independent of $k$. A bound $\lvert x\rvert^k$ is polynomial for each fixed $k$ but is not generally an FPT bound; it belongs to the broader slice-wise polynomial, or XP, style of running time.
The parameterized counting hierarchy $\#\mathrm W[t]$ formalizes hardness under parameter-respecting counting reductions. Counting $k$-cliques is a canonical $\#\mathrm W[1]$-complete problem, and counting fixed-length paths and cycles also has established parameterized hardness despite tractable parameterized decision versions. Primary source: Flum and Grohe. Proof scope: the hardness reductions and formal hierarchy definitions are omitted; no unconditional separation from FPT is asserted.
Solved example. A four-cycle has four vertex-subset edges, so the count of two-cliques is four; the count of three-cliques is zero. Enumerating all $\binom Nk$ vertex subsets and checking their pairs costs $O(N^kk^2)$ in a direct implementation. This is a valid exact algorithm, but its exponent depends on $k$.
Changing the parameter can make the same family tractable. For independent-set counting on a graph with a supplied tree decomposition of width $w$, dynamic programming stores selected/unselected states for each bag and rejects states containing an edge. There are at most $2^{w+1}$ bag states; introduce, forget, and join steps combine exact counts. This gives an FPT counting algorithm in $w$, with integer bit costs included. Omitted prerequisite: the full nice-decomposition recurrence and its boundary-state proof; a path instance is checked directly below.
Exercise. Count independent sets of a four-vertex path. Hint: if $a_j$ is the count on $j$ vertices, condition on the last vertex. Solution: $a_0=1,a_1=2$, and $a_j=a_{j-1}+a_{j-2}$, giving $a_2=3,a_3=5,a_4=8$. This width-one model illustrates an efficient count without classifying arbitrary graphs.
48.8 Constraint-satisfaction counting problems
Optional extension; not required to complete the chapter foundation.
Fix a finite domain $D$ and a finite relation language $\Gamma$. An instance of $\#\mathrm{CSP}(\Gamma)$ declares variables and imposes constraints $R(x_{i_1},\ldots,x_{i_a})$ with $R\in\Gamma$. The output counts all assignments satisfying every constraint. The language is fixed rather than part of each input. Repeated variables, constants, and allowed weights are conventions to state, not harmless omissions.
For Boolean affine relations, each constraint is a system of linear equations over $\mathbb F_2$. Combining them gives $Ax=b$. Gaussian elimination either finds inconsistency, giving zero, or finds rank $r$ on $n$ variables, giving exactly $2^{n-r}$ assignments. This is a complete algorithm: free-variable choices uniquely determine pivot variables.
Solved example. The constraints $x+y=0$ and $y+z=1$ modulo two have rank two on three variables. Taking $y=0$ gives $001$ and taking $y=1$ gives $110$, so the count is two. An extra unconstrained variable doubles it, and an inconsistent equation $x+y=1$ added to the first system makes the count zero.
For comparison, the binary OR relation is $R=\{01,10,11\}$. Imposing it on each graph edge asks that every edge have at least one endpoint assigned one. The zero-assigned vertices are exactly an independent set, giving a bijection with independent sets of the graph. On a triangle, the models are $111,011,101,110$, so the count is four even though finding one model is trivial: use all ones.
The exact Boolean-language classification is the established Creignou–Hermann theorem, stated precisely in section 48.10. This section proves the affine algorithm and the OR/independent-set bijection; it does not derive a dichotomy for weighted, larger-domain, planar, or approximate counting problems.
Exercise. Show that binary OR is not affine. Hint: an affine subset of $\mathbb F_2^a$ is closed under the xor of any three of its elements. Solution: $01\oplus10\oplus11=00$, which is excluded. The relation has three tuples, also incompatible with the power-of-two size of a nonempty affine subspace translate.
48.9 Algebraic and holographic counting algorithms
Optional extension; not required to complete the chapter foundation.
The bridge from recommended section 28.4 is that a counting expression can be organized by algebraic cancellation rather than by listing solutions. The elementary contraction identity supplied here is sufficient to follow this extension; the full primary holographic treatment is Valiant's Holographic Algorithms. The recommended background is not an entry requirement.
A tensor-network or Holant expression assigns a Boolean state to each edge, multiplies local signature values, and sums over all edge assignments. Insert an invertible basis matrix on one end of a contracted index and its inverse on the other; the contraction remains unchanged. This preserves the aggregate sum, even when the transformed entries are negative and no one-to-one correspondence survives.
Solved example. Take column vectors $f=(1,2)^{\mathsf T}$ and $g=(3,4)^{\mathsf T}$. Their contraction is $f^{\mathsf T}g=11$. With
$$T=\begin{pmatrix}1&1\\ 1&-1\end{pmatrix},\qquad T^{-1}=T/2,$$
use $f'=Tf=(3,-1)^{\mathsf T}$ and $g'=T^{-\mathsf T}g=(7/2,-1/2)^{\mathsf T}$. Then $f'^{\mathsf T}g'=21/2+1/2=11$. In general $(Tf)^{\mathsf T}(T^{-\mathsf T}g)=f^{\mathsf T}g$. Applying this consistently to every contracted tensor index proves the aggregate invariance. This alone does not make tensor contraction polynomial-time; it must transform the local signatures into a tractable class.
For planar matching counts, a skew-symmetric matrix $K$ with a suitable Pfaffian orientation satisfies $\operatorname{Pf}(K)^2=\det K$, and the orientation aligns the signs of matching contributions. On a four-cycle, choose $K_{12}=K_{23}=K_{34}=K_{14}=1$, set $K_{ji}=-K_{ij}$, and set nonedge entries to zero. Then
$$\operatorname{Pf}(K)=K_{12}K_{34}-K_{13}K_{24}+K_{14}K_{23}=2,\qquad\det K=4.$$
The two perfect matchings are counted with the same sign. The established planar Pfaffian algorithm and matchgate machinery require planarity and compatible signatures. Omitted prerequisites: finding a Pfaffian orientation and the matchgate identities; arbitrary graph signatures and arbitrary basis changes are not claimed tractable. Rational arithmetic sizes must also be tracked when applying such transformations.
Exercise. Change $K_{14}$ from one to minus one in the four-cycle example. Hint: recompute the two matching terms. Solution: the Pfaffian becomes zero. The graph still has two matchings, but their signs cancel, showing why an appropriate orientation is necessary.
48.10 Complexity dichotomy theorems
Optional extension; not required to complete the chapter foundation.
A dichotomy theorem divides a precisely defined family of problems into tractable and complete cases. It does not mean that every counting problem in mathematics has only two possible complexities.
Here is the established exact unweighted Boolean $\#\mathrm{CSP}$ dichotomy of Creignou and Hermann. Fix a finite set $\Gamma$ of Boolean relations. An instance is a conjunction of applications of those relations to declared Boolean variables, with repeated variables permitted. If every relation in $\Gamma$ is affine, solution counting is in $\mathrm{FP}$. Otherwise it is $\#\mathrm P$-complete under polynomial-time counting Turing reductions. Empty inconsistent relations can be handled as immediately unsatisfiable; nonempty affine relations are solution sets of linear equations over $\mathbb F_2$.
Proof mechanism and omitted prerequisites. The tractable branch is exactly the Gaussian-elimination argument in section 48.8. The hardness branch uses closure properties of relation languages and gadgets to realize hard counting relations, with the appropriate counting reductions. The full algebraic language classification and hardness gadgets are omitted. They cannot be replaced by a decision reduction that ignores auxiliary multiplicities. This is an established theorem for exact counts; its statement does not provide an approximation dichotomy or a planar restriction theorem.
Solved example. A language consisting of parity and equality relations is affine, so its constraints produce a linear system and a count $2^{n-r}$ or zero. Adding binary OR makes the language nonaffine and places general exact counting in the complete branch. OR-only formulas are always satisfiable by all ones, but their number of models is the independent-set count of a graph. This explains why the theorem's counting reductions are not silently being called parsimonious reductions from every satisfiability problem.
A fixed instance from a hard language may still be easy: the triangle OR instance has four models that can be listed immediately. Completeness concerns an unbounded family of encoded inputs. Conversely, an exact tractability theorem requires a polynomial algorithm on all inputs in its stated class, not success on a few small examples.
Exercise. Does the theorem classify a problem where arbitrary rational-valued constraint functions are included in the input? Hint: compare the domain, weights, and fixed-language hypothesis. Solution: no. Weighted signatures supplied as input change the problem family and encoding. A weighted dichotomy needs its own hypotheses and theorem; neither this Boolean relation theorem nor an exact result automatically transfers to it.
Prove a counting reduction and verify its effect on solution multiplicity
The investigation reconstructs a parsimonious gate reduction and tests its fibers. It connects $\#\mathrm P$ witness counting to the role of gadgets in dichotomy proofs: a gadget is valid only when its auxiliary solution counts support the asserted reduction. In probabilistic inference and configuration analysis, model counts quantify how many admissible states remain; an unnoticed multiplicity factor changes probabilities even when feasibility is preserved.
Prove a counting reduction and verify its effect on solution multiplicity
Inputs and deliverables. Declare source variables $x,y,z$ and use
$$F(x,y,z)=(x\lor y)\land(\neg x\lor z).$$
Introduce auxiliary variables $u,v,w$ with $u=x\lor y$, $v=\neg x\lor z$, and $w=u\land v$, then require $w=1$. Submit the target clauses, a source-to-target correspondence, every fiber size, exact counts, and a classification of the reduction. Use full declared-variable assignments throughout.
Warm-up — 20 points. Evaluate the eight source assignments. Worked solution: the satisfying triples $xyz$ are $010,011,101,111$. If $x=0$, $y$ must be one and $z$ is free; if $x=1$, $z$ must be one and $y$ is free. Thus $\#F=4$.
Proof — 30 points. Use the target formula
$$\begin{aligned} \Psi={}&(\neg x\lor u)\land(\neg y\lor u)\land(x\lor y\lor\neg u)\\ &\land(x\lor v)\land(\neg z\lor v)\land(\neg x\lor z\lor\neg v)\\ &\land(\neg w\lor u)\land(\neg w\lor v)\land(\neg u\lor\neg v\lor w)\land(w). \end{aligned}$$
Prove that each satisfying source assignment has exactly one satisfying target extension, and that every target model projects to a satisfying source assignment. Hints: prove the OR and AND truth tables separately; process the circuit in gate order.
Worked solution. The first three clauses force $u=x\lor y$. The next three force $v=\neg x\lor z$. The AND clauses force $w=u\land v$. Hence every source assignment has exactly one gate-consistent auxiliary assignment, and the final unit clause accepts it exactly when $F=1$. For each of the four source models, $(u,v,w)=(1,1,1)$. Nonmodels have no extension satisfying the asserted output. Projection and unique extension are inverse maps, proving $\#\Psi=\#F=4$. This is parsimonious, not merely equisatisfiable.
Exact computational audit — 35 points. Enumerate all eight source assignments and all eight auxiliary triples for each, for sixty-four complete target assignments. Check every clause, record each source fiber, and verify the following table:
| Source $xyz$ | Target models above it |
|---|---|
| $000$ | $0$ |
| $001$ | $0$ |
| $010$ | $1$ |
| $011$ | $1$ |
| $100$ | $0$ |
| $101$ | $1$ |
| $110$ | $0$ |
| $111$ | $1$ |
Then deliberately append a fresh unrestricted declared variable $t$, represented by the tautology $(t\lor\neg t)$. The target count becomes eight with fiber size two above each source model. Recovering four by dividing by two is valid, but the modified transformation is not parsimonious. Finally remove the unit output clause $(w)$ from the original target: all eight source inputs have one gate-consistent extension, so the count is eight, including nonmodels of $F$. This second error is not repaired by an unexplained factor-two claim, because it changes which source assignments survive.
Validation and complexity. Verify each gate truth table on every input/output combination; this proves the local property for arbitrary circuit occurrences. For a circuit with $g$ gates, the construction adds one variable per gate, at most three clauses per binary gate and two per NOT gate, plus one output clause. Its size and construction time are linear in the circuit description up to ordinary encoding costs. The unique-extension induction is the general correctness proof; the sixty-four-assignment audit verifies the supplied instance only. Do not infer the full $\#\mathrm P$-completeness theorem from that enumeration.
Interpretation — 15 points. Explain the difference between counting witnesses, testing existence, exact oracle reductions, and approximation-preserving reductions. Connect the unique-extension proof to complexity dichotomies: the affine branch gives a global exact algorithm, whereas hardness gadgets in a nonaffine language need a rigorously stated reduction and multiplicity accounting. In probabilistic model counting with uniformly weighted input assignments, $F$ has probability $4/8=1/2$. For $\Psi$ sampled uniformly on its six declared variables, the satisfaction probability is $4/64=1/16$: equal model counts do not preserve uniform-assignment probabilities when the dimension changes. A transformed representation must preserve the intended measure or include the proved normalization correction.
Optional matching extension, ungraded. Enumerate the six permutations for the foundation matrix, verify permanent three and determinant minus one, and use the subset dynamic program to reproduce the permanent. Try the uniform-permutation estimator and compare its empirical variance with the proved relative factor $1/M$. Solution outline: only $123,132,213$ survive; their signs are $+,-,-$. The estimator takes values zero and six with equal probability, so mean is three and variance is nine. Its empirical behavior is evidence for this finite distribution; the FPRAS theorem requires the separate general mixing analysis.
Optional randomized-restriction extension, ungraded. For the four source models, enumerate the sixteen affine maps $h(x,y,z)=a_1x+a_2y+a_3z+b$ to one bit. Count the models in the zero bucket and verify that $2Z_h$ has mean four and variance four over uniform seeds. Solution outline: each model survives with probability one-half and any two survive independently. Thus $\mathbb E Z_h=2$, $\operatorname{Var}Z_h=1$, and scaling by two gives the stated values. Individual bucket counts need not equal half the original count, so this is an unbiased randomized identity rather than a parsimonious map.
Rubric and scope. Award warm-up points for declared-variable counts; proof points for both correspondence directions and uniqueness; audit points for all fibers, both deliberate errors, and construction size; interpretation points for reduction type and measure preservation. Check sign, weight, domain, approximation, and parameter assumptions before applying a cited theorem. The exact completeness, FPRAS, parameterized, holographic, and Boolean dichotomy results are established, with omitted prerequisites stated in their sections; no unproved class separation is needed to complete the investigation.
Next in the Series
In Chapter 49: Combinatorics in Algorithms, Learning and Optimization, we'll explore Connect set-system dimensions and discrete structure to computational learning.