47.02.07 · theoretical-cs / 02-complexity-fundamentals

#P, Counting, the Permanent, and Toda's Theorem

shipped3 tiersLean: nonepending prereqs

Anchor (Master): Arora and Barak 2009 Computational Complexity: A Modern Approach (Cambridge) §17.1-17.4 (#P and its structural properties, Valiant's theorem that the permanent is #P-complete, Toda's theorem with the full proof via probabilistic reductions and the pumping lemma, and connections to interactive proofs and hardness of approximation)

Intuition Beginner

In NP problems, the question is "does at least one solution exist?" A different question is "how many solutions exist?" This is a counting problem, and it is often much harder than the existence question.

Think of a jigsaw puzzle. Asking "can this puzzle be solved?" is an existence question. Asking "in how many different ways can this puzzle be solved?" is a counting question. The second question contains the answer to the first (if the count is zero, no solution exists), but it also gives much more information.

The class #P (pronounced "sharp P") captures this counting perspective. A function is in #P if it counts the number of accepting computation paths of a polynomial-time nondeterministic machine. This is the counting analogue of NP: NP asks whether the count is positive, while #P asks for the exact count.

A remarkable theorem by Toda shows that #P is at least as powerful as the entire polynomial hierarchy. Any problem that can be expressed with any number of alternating "there exists" and "for all" quantifiers can be solved with a single query to a #P oracle. This means counting is extraordinarily powerful — far more powerful than mere existence.

The permanent of a matrix, a simple-looking algebraic expression that swaps the signs in the determinant, turns out to be #P-complete. Computing it is as hard as any counting problem.

Visual Beginner

The relationship between NP, #P, and the polynomial hierarchy.

               P^#P
              / |  \
            PH  |   \
           /|\  |    \
          / | \ |     \
         P  NP  coNP   ...

Toda's theorem says the entire polynomial hierarchy (PH) sits inside P with access to a #P oracle. The permanent function is #P-complete: it encodes every counting problem.

concept	NP version	#P version
SAT	is there a satisfying assignment?	how many satisfying assignments?
matching	is there a perfect matching?	how many perfect matchings?
paths	is there a path from s to t?	how many paths from s to t?

Worked example Beginner

Consider a 3-CNF formula $ϕ$ with three variables and two clauses: $(x_{1} \lor x_{2} \lor x_{3}) \land (\neg x_{1} \lor \neg x_{2} \lor x_{3})$ .

The SAT question: is at least one of the 8 possible assignments satisfying? Let us check. Assignment $(0, 0, 1)$ gives both clauses true. Assignment $(1, 1, 1)$ gives first clause true, second clause false. So yes, $ϕ$ is satisfiable.

The #SAT question: how many satisfying assignments are there? Checking all 8: $(0, 0, 0)$ fails clause 1. $(0, 0, 1)$ satisfies both. $(0, 1, 0)$ satisfies both. $(0, 1, 1)$ satisfies both. $(1, 0, 0)$ satisfies both. $(1, 0, 1)$ satisfies both. $(1, 1, 0)$ fails clause 2. $(1, 1, 1)$ fails clause 2. Total: 5 satisfying assignments.

The #SAT function maps $ϕ$ to 5. This function is in #P: a nondeterministic machine guesses an assignment and verifies it in polynomial time, and the number of accepting paths equals the number of satisfying assignments. The #P-completeness of #SAT means every #P function reduces to counting satisfying assignments.

Check your understanding Beginner

Formal definition Intermediate+

A function $f : {0, 1}^{*} \to N$ is in #P if there exists a polynomial-time nondeterministic Turing machine $M$ such that for every input $x$ ,

f (x) = ∣ {accepting computation paths of M on x} ∣.

The class $# P$ is a function class, not a language class. To relate it to decision classes, define $P^{# P}$ as the class of languages decidable by a polynomial-time deterministic Turing machine with oracle access to a function in $# P$ : the machine may write a query $q$ on a special tape, receive $f (q)$ as the answer, and use it in subsequent computation. Define $PP$ (probabilistic polynomial time) as the class of languages $L$ for which there exists a polynomial-time probabilistic Turing machine $M$ such that $x \in L ⟺ Pr [M (x) accepts] > 1/2$ .

The permanent of an $n \times n$ matrix $A$ is

perm (A) = σ \in S_{n} \sum i = 1 \prod n A_{i, σ (i)},

where $S_{n}$ is the symmetric group on ${1, \dots, n}$ . Unlike the determinant, the permanent omits the sign factor $sgn (σ)$ . This seemingly small change has enormous computational consequences: the determinant is computable in polynomial time by Gaussian elimination, but the permanent is #P-complete ^{[Arora-Barak §17.2]}.

A parsimonious reduction from $# P$ function $f$ to $# P$ function $g$ is a polynomial-time computable function $h$ with $f (x) = g (h (x))$ for all $x$ . A polynomial-time Turing reduction from $f$ to $g$ is a polynomial-time oracle machine computing $f$ with access to $g$ .

Counterexamples to common slips Intermediate+

"#P is just NP with counting." The distinction is subtler. NP is a class of languages (decision problems); #P is a class of functions. A #P function gives the exact number of witnesses, which contains more information than the mere existence question that NP asks. The decision version "is the count positive?" gives NP, but recovering the exact count from NP queries may require exponentially many queries.
"The permanent is the determinant without signs, so it should be equally easy to compute." The sign in the determinant enables row-reduction (Gaussian elimination) without changing the answer. Without the sign, row operations can change the permanent, so the efficient algorithm breaks down entirely. Valiant's theorem shows the permanent is #P-complete even for 0-1 matrices.
"Toda's theorem means PH collapses." It does not. Toda's theorem places PH inside $P^{# P}$ , but $P^{# P}$ could be much larger than PH. The theorem shows that counting is powerful, not that the hierarchy collapses. A collapse would mean some level $Σ_{k}$ equals $Σ_{k + 1}$ .

Key theorem with proof Intermediate+

Theorem (Valiant, 1979). The permanent of 0-1 matrices is #P-complete under polynomial-time reductions.

Proof sketch. Membership in #P: the permanent of an $n \times n$ matrix $A$ equals the number of perfect matchings in the weighted bipartite graph defined by $A$ . A nondeterministic machine guesses a permutation $σ$ and verifies that $\prod_{i} A_{i, σ (i)} = 1$ , accepting if so. The number of accepting paths is $perm (A)$ .

Hardness: reduce #3SAT to the permanent. Given a 3-CNF formula $ϕ$ with $n$ variables and $m$ clauses, construct an integer matrix $A$ such that $perm (A) = 4^{3 m} \cdot ∣ {satisfying assignments} ∣$ . The construction uses a graph whose cycle covers encode variable assignments and clause satisfactions. Each variable $x_{i}$ is represented by a gadget with two possible traversal modes (true or false). Each clause is a gadget that contributes a weight of 1 for each satisfied literal. The matrix entries are 0 or 1, and the permanent counts exactly the number of satisfying assignments, up to a known multiplicative factor that can be divided out. The construction is polynomial in $n + m$ . $□$

Theorem (Toda, 1991). $PH \subseteq P^{# P}$ .

Proof sketch. The proof has two stages. Stage 1: show $Σ_{k} \subseteq BP \cdot \oplus \cdot P$ for every $k$ , where $BP \cdot \oplus \cdot P$ is the class of languages for which there exists a polynomial-time predicate $R$ such that $x \in L \Rightarrow Pr_{y} [∣ {z : R (x, y, z)} ∣ is odd] \geq 2/3$ and $x \in / L \Rightarrow Pr_{y} [∣ {z : R (x, y, z)} ∣ is odd] \leq 1/3$ . Stage 2: show $BP \cdot \oplus \cdot P \subseteq P^{# P}$ .

Stage 1 uses the Valiant-Vazirani lemma: given a Boolean formula $ϕ$ , one can produce a formula $ψ$ (by adding random constraints) such that if $ϕ$ is unsatisfiable then $ψ$ is unsatisfiable, and if $ϕ$ has at least one satisfying assignment then $ψ$ has exactly one with probability $\geq 1/ n$ . This "isolation" converts a "there exists" quantifier into a parity constraint, and the probability boost is handled by amplification ^{[Arora-Barak §17.3]}.

Stage 2: computing $Pr_{y} [∣ {z : R (x, y, z)} ∣ is odd]$ reduces to a single #P query, since the probability is a ratio of counts that can be extracted from a #P oracle. $□$

Bridge. This theorem is the foundational reason counting is more powerful than alternating quantification: a single #P query captures the entire polynomial hierarchy, and this is exactly the structural insight that makes the permanent such a potent computational object — it encodes every counting problem into a purely algebraic expression. The isolation lemma of Valiant-Vazirani builds toward the PCP theorem 47.03.05 where similar hashing techniques isolate witness structures, and the counting perspective appears again in the FPRAS algorithms 47.05.04 where approximate counting for #P-complete problems like the permanent becomes feasible when randomisation is allowed. The central insight is that parity (counting modulo 2) plus randomisation already captures existential quantification, and putting these together through the Toda pipeline, the entire quantifier hierarchy is swallowed by a single counting query. The bridge is that the permanent, as the simplest algebraic expression that is #P-complete, connects the discrete world of Boolean satisfiability to the continuous world of linear algebra, and this connection generalises to the entire theory of algebraic complexity.

Exercises Intermediate+

Exercise 6 (hard, symbolic).

Prove that $PP \subseteq P^{# P}$ , where $PP$ is the class of languages decidable by a probabilistic polynomial-time machine with error probability $< 1/2$ (unbounded gap from 1/2).

Hint

The acceptance probability of a PP machine is a ratio of counts, which can be computed with a #P query.

Answer

A PP machine $M$ on input $x$ has $N = 2^{p (∣ x ∣)}$ possible random strings. Let $a (x)$ be the number of random strings leading to acceptance. Then $x \in L$ iff $a (x) > N /2$ . The function $a (x)$ is in #P: the nondeterministic machine guesses a random string $r$ and simulates $M (x, r)$ , accepting iff $M$ accepts. So $a (x) = # acc (x)$ is a #P function. A $P^{# P}$ machine queries the oracle for $a (x)$ and $N = 2^{p (∣ x ∣)}$ , then checks whether $a (x) > N /2$ . This is a single #P query with polynomial post-processing. Hence $PP \subseteq P^{# P}$ . Rubric: full credit for identifying $a (x)$ as a #P function and the threshold comparison.

Exercise 8 (hard, symbolic).

Let $MAJ$ -SAT denote the language of Boolean formulas for which more than half of all assignments are satisfying. Show that $MAJ$ -SAT is PP-complete.

Hint

Reduce an arbitrary PP computation to MAJ-SAT by encoding random strings as variable assignments.

Answer

Membership: a PP machine on input $ϕ$ with $n$ variables has $2^{n}$ possible assignments. The question "are more than half satisfying?" is decided by a PP machine that picks a random assignment and checks it, accepting iff the assignment satisfies $ϕ$ . The acceptance probability exceeds 1/2 iff more than half the assignments satisfy $ϕ$ .

Hardness: let $L \in PP$ via machine $M$ using $p (n)$ random bits. Construct a Boolean formula $ψ (x, r)$ that is true iff $M$ accepts $x$ using random string $r$ . The number of satisfying assignments of $ψ$ (treating $x$ as fixed constants) equals the number of accepting random strings. So $x \in L$ iff more than half of the $2^{p (∣ x ∣)}$ assignments to $r$ satisfy $ψ$ , i.e., $ψ$ is in MAJ-SAT. The reduction is polynomial-time. Rubric: full credit for both directions.

Advanced results Master

The theory of #P extends beyond the foundational theorems into structural complexity, algebraic methods, and the surprising power of approximate counting.

Theorem 1 (Valiant's theorem, detailed). The reduction from #3SAT to the permanent constructs a matrix $A$ of size $O (n + m)$ for a formula with $n$ variables and $m$ clauses. Each variable gadget is a subgraph with two cycle-cover modes: one corresponding to "true" and one to "false." Clause gadgets connect to the variable gadgets through edges that are present only when the corresponding literal satisfies the clause. The permanent of $A$ counts cycle covers of the resulting graph, which are in bijection with pairs (variable assignment, clause satisfaction pattern). A carefully designed weighting scheme ensures that only satisfying assignments contribute non-zero weight, and each contributes $4^{3 m}$ . Dividing by $4^{3 m}$ gives the exact count of satisfying assignments ^{[Arora-Barak §17.2]}.

Theorem 2 (PP-completeness of MAJ-SAT). The language MAJ-SAT $= {ϕ : more than half of all assignments satisfy ϕ}$ is PP-complete. More generally, $PP$ captures "threshold" decision problems: does a count exceed a specified fraction? The PP hierarchy collapses ( $PP^{PP} = PP$ ), unlike the polynomial hierarchy which is not known to collapse. This makes PP structurally simpler than PH despite being computationally powerful ^{[Arora-Barak §17.3]}.

Theorem 3 (Toda's theorem, proof outline). The proof proceeds in three steps. Step 1: the Valiant-Vazirani isolation lemma converts a SAT instance $ϕ$ into a formula $ψ$ such that if $ϕ$ is unsatisfiable then $ψ$ is unsatisfiable, and if $ϕ$ is satisfiable then $ψ$ has exactly one satisfying assignment with probability $Ω (1/ n)$ . Step 2: this converts existential quantification into parity ( $\oplus P$ ), since "exactly one satisfying assignment" is detected by parity. Step 3: iterate this conversion across all quantifier levels, using amplification to boost the success probability at each level. The final result is that any $Σ_{k}$ predicate reduces to a $BP \cdot \oplus P$ predicate, and $BP \cdot \oplus P \subseteq P^{# P}$ by computing the relevant counts exactly ^{[Arora-Barak §17.3]}.

Theorem 4 (permanent for matrices with non-negative entries). While the permanent of general 0-1 matrices is #P-complete, the permanent of matrices with non-negative entries can be approximated efficiently. The Jerrum-Sinclair-Vigoda algorithm (2004) gives an FPRAS (fully polynomial-time randomised approximation scheme) for the permanent of matrices with non-negative entries. This is a rare example of a #P-complete problem that admits efficient approximation, connecting to 47.05.04.

Theorem 5 (algebraic characterisation). The permanent can be expressed as a multivariate polynomial: $perm (A) = \sum_{σ} \prod_{i} x_{i, σ (i)}$ where the matrix entries are variables. This polynomial has degree $n$ in $n^{2}$ variables. The theory of arithmetic circuits studies the complexity of computing such polynomials, and the permanent plays a role analogous to SAT in algebraic complexity. The VP versus VNP question (the algebraic analogue of P versus NP) asks whether the permanent polynomial can be computed by polynomial-size arithmetic circuits ^{[Arora-Barak §17.4]}.

Synthesis. The foundational reason #P is so powerful is that a single count encodes exponentially many bits of information about the structure of a computation, and this is exactly what Toda's theorem exploits: the entire polynomial hierarchy, built from unbounded quantifier alternation, collapses into a single counting query. The Valiant-Vazirani isolation lemma builds toward the PCP theorem 47.03.05 and appears again in the design of interactive proof systems 47.03.04 where isolating witnesses is a key technique. The central insight is that parity plus randomisation can simulate existential quantification, and putting these together through iteration, any fixed level of the hierarchy is captured. The bridge is that the permanent, as the simplest #P-complete problem, connects combinatorial counting to algebra, and this connection generalises through the theory of arithmetic circuits to the VP versus VNP question, which is dual to the P versus NP question in the algebraic setting. The #P framework also appears in the derandomisation programme 47.05.05, where approximate counting via random walks provides efficient algorithms for special cases.

Full proof set Master

Proposition 1 (#SAT is #P-complete). The function $# SAT (ϕ) = ∣ {satisfying assignments of ϕ} ∣$ is #P-complete under parsimonious reductions.

Proof. Membership: a nondeterministic polynomial-time machine on input $ϕ$ with $n$ variables guesses an assignment $a \in {0, 1}^{n}$ and evaluates $ϕ (a)$ . It accepts iff $ϕ (a)$ is true. The number of accepting paths equals the number of satisfying assignments.

Completeness: let $f \in # P$ via machine $M$ with $p (n)$ nondeterministic choices. By the Cook-Levin construction 47.02.02, there is a formula $ϕ_{M, x}$ such that satisfying assignments of $ϕ_{M, x}$ are in bijection with accepting paths of $M$ on $x$ . The bijection is parsimonious (preserves counts). Hence $f (x) = # SAT (ϕ_{M, x})$ . $□$

Proposition 2 (permanent is in #P). The permanent of an $n \times n$ matrix $A$ with non-negative integer entries is in #P.

Proof. A nondeterministic machine guesses a permutation $σ \in S_{n}$ and computes $\prod_{i = 1}^{n} A_{i, σ (i)}$ . It accepts with multiplicity equal to this product (achieved by branching). The total number of accepting paths is $\sum_{σ} \prod_{i} A_{i, σ (i)} = perm (A)$ . $□$

Proposition 3 (PP within P^#P). $PP \subseteq P^{# P}$ .

Proof. Let $L \in PP$ via machine $M$ using $p (n)$ random bits. The number $a (x)$ of accepting random strings is a #P function. Query the #P oracle for $a (x)$ and compare to $2^{p (∣ x ∣) - 1}$ . If $a (x) > 2^{p (∣ x ∣) - 1}$ , accept; else reject. This uses one #P query and polynomial post-processing. $□$

Proposition 4 (PH within BP . $\oplus$ . P). For every $k$ , $Σ_{k}^{P} \subseteq BP \cdot \oplus \cdot P$ .

Proof sketch. By induction on $k$ . Base case $k = 1$ : $Σ_{1} = NP$ . Given a formula $ϕ$ , apply Valiant-Vazirani to obtain $ψ$ with the isolation property. Then $ϕ \in SAT$ iff with probability $\geq 1/ n$ over the random hash function, $ψ$ has exactly one satisfying assignment (detected by parity). This gives $NP \subseteq BP \cdot \oplus \cdot P$ .

Inductive step: $Σ_{k} = \exists\forall \dots$ . Apply isolation to the outermost existential quantifier, converting it to BP and parity. The inner quantifiers are handled by the induction hypothesis. Amplification boosts the success probability at each level. $□$

Proposition 5 (BP . $\oplus$ . P within P^#P). $BP \cdot \oplus \cdot P \subseteq P^{# P}$ .

Proof. A language $L \in BP \cdot \oplus \cdot P$ has a polynomial-time predicate $R$ such that for $x \in L$ , $Pr_{y} [∣ {z : R (x, y, z)} ∣ is odd] \geq 2/3$ , and for $x \in / L$ the probability is $\leq 1/3$ . The quantity $Pr_{y} [odd parity]$ is computable from two #P queries: (a) count pairs $(y, z)$ with $R (x, y, z)$ , and (b) count pairs $(y, z_{1}, z_{2})$ with $R (x, y, z_{1}) \land R (x, y, z_{2})$ , which lets us extract the parity information. The comparison to the threshold $1/2$ is a polynomial-time post-processing step. $□$

Connections Master

NP-completeness 47.02.02 provides the Cook-Levin reduction that underlies #P-completeness. The parsimonious version of Cook-Levin preserves witness counts, making #3SAT #P-complete. The entire #P theory is the counting extension of the NP-completeness framework.
Probability spaces and Kolmogorov axioms 37.01.01 provide the measure-theoretic foundation for PP and the probabilistic analysis in Toda's theorem. The threshold behaviour of PP ("accept if probability exceeds 1/2") is a measure comparison.
Interactive proofs 47.03.04 connect to #P through the LFKN protocol and the IP = PSPACE proof. The counting techniques developed for #P (especially the sum-check protocol) are central to the interactive proof machinery.
FPRAS for counting 47.05.04 studies efficient approximation algorithms for #P-complete problems. The permanent of non-negative matrices admits an FPRAS, showing that approximate counting can be easier than exact counting.

Historical & philosophical context Master

Leslie Valiant proved the #P-completeness of the permanent in 1979, in his paper "The Complexity of Computing the Permanent" published in Theoretical Computer Science. The result was striking because the permanent is a simple algebraic expression — just the determinant without signs — yet it captures the full difficulty of counting. The construction introduced the cycle-cover method for encoding Boolean constraints into matrix entries, a technique that has become standard in algebraic complexity ^{[Arora-Barak §17.2]}.

Seinosuke Toda proved his theorem in 1991, in "PP is Harder than the Polynomial-Time Hierarchy" (SIAM Journal on Computing). The result was unexpected: it showed that counting is strictly more powerful than any fixed level of quantifier alternation, giving the first tight connection between counting classes and the polynomial hierarchy. The proof introduced the use of the Valiant-Vazirani isolation lemma as a tool for converting quantifiers into parity constraints.

The development of FPRAS algorithms for counting, culminating in the Jerrum-Sinclair-Vigoda algorithm for the permanent (2004), showed that approximate counting is sometimes feasible even when exact counting is #P-complete. This opened the field of approximate counting, connecting complexity theory to practical algorithm design.

Bibliography Master

@article{valiant1979complexity,
  author  = {Valiant, Leslie G.},
  title   = {The complexity of computing the permanent},
  journal = {Theoretical Computer Science},
  volume  = {8},
  number  = {2},
  year    = {1979},
  pages   = {189--201}
}

@article{toda1991pp,
  author  = {Toda, Seinosuke},
  title   = {{PP} is harder than the polynomial-time hierarchy},
  journal = {SIAM Journal on Computing},
  volume  = {20},
  number  = {5},
  year    = {1991},
  pages   = {865--877}
}

@article{valiant1986np,
  author  = {Valiant, Leslie G. and Vazirani, Vijay V.},
  title   = {{NP} is as easy as detecting unique solutions},
  journal = {Theoretical Computer Science},
  volume  = {47},
  year    = {1986},
  pages   = {85--93}
}

@article{jerrum2004polynomial,
  author  = {Jerrum, Mark and Sinclair, Alistair and Vigoda, Eric},
  title   = {A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries},
  journal = {Journal of the ACM},
  volume  = {51},
  number  = {4},
  year    = {2004},
  pages   = {671--697}
}

@book{arora2009computational,
  author    = {Arora, Sanjeev and Barak, Boaz},
  title     = {Computational Complexity: A Modern Approach},
  publisher = {Cambridge University Press},
  year      = {2009}
}

Prerequisites

47.02.02 pending
37.01.01 pending

Tier anchors

beginner: Arora and Barak 2009 Computational Complexity: A Modern Approach (Cambridge) §17.1 (the idea of counting solutions rather than just asking whether one exists, and why this is harder)
intermediate: Arora and Barak 2009 Computational Complexity: A Modern Approach (Cambridge) §17.1-17.3 (the class #P, #P-completeness, the permanent of a matrix and Valiant's theorem, and Toda's theorem that $PH \subseteq P^{# P}$ )
master: Arora and Barak 2009 Computational Complexity: A Modern Approach (Cambridge) §17.1-17.4 (#P and its structural properties, Valiant's theorem that the permanent is #P-complete, Toda's theorem with the full proof via probabilistic reductions and the pumping lemma, and connections to interactive proofs and hardness of approximation)

References

Arora, S. and Barak, B. — Computational Complexity: A Modern Approach · Cambridge University Press (2009). §17.1 defines the class $# P$ as the class of functions $f : {0, 1}^{*} \to N$ where $f (x)$ equals the number of accepting paths of a polynomial-time nondeterministic Turing machine on input $x$ , distinguishes $# P$ from decision classes by noting that $# P$ is a class of functions not languages, defines $# P$ -completeness under polynomial-time Turing reductions and under parsimonious reductions; §17.2 presents Valiant's 1979 theorem that the permanent $perm (A) = \sum_{σ \in S_{n}} \prod_{i = 1}^{n} A_{i, σ (i)}$ is $# P$ -complete even for 0-1 matrices, with the proof constructing a reduction from $#3 S A T$ to the permanent by encoding variable assignments and clause satisfactions as matrix entries and using cycle covers to ensure correct counting; §17.3 states and proves Toda's theorem $PH \subseteq P^{# P}$ by first showing $P^{# P} = P^{PP}$ and then using a randomised reduction from any $Σ_{k}$ predicate to a single $# P$ query, with derandomisation via the Valiant-Vazirani isolation lemma.

Estimated time

beginner: 15m
intermediate: 50m
master: 95m