P

The class of counting problems associated with NP decision problems. Formally, a function $f:\{0,1{\}}^{\ast }\to \mathbb{N}$ is in $\#P$ if there exists a nondeterministic polynomial-time Turing machine $M$ such that $f(x)$ equals the number of accepting computation paths of $M$ on input $x$.

Where NP asks “does a solution exist?”, $\#P$ asks “how many solutions exist?” The counting version of a problem can be dramatically harder than the decision version.

See the complexity zoo entry here.

Known relationships

• Every $\#P$ function can be computed in polynomial time with a PP oracle: $\#P\subseteq {\text{classFP}}^{\mathbf{PP}}$.
• Toda’s theorem: $\mathbf{PH}\subseteq {\mathbf{P}}^{\#P}$ — TODO citation (Toda 1991). The entire polynomial hierarchy can be decided in polynomial time with access to a single $\#P$ oracle, which is a remarkable collapse of complexity.
• $\#P$-hardness implies NP-hardness (under polynomial-time Turing reductions): if you can count solutions in polynomial time, you can certainly decide existence.
• Approximate counting (computing a $(1\pm \epsilon )$-multiplicative approximation) is sometimes feasible when exact counting is $\#P$-hard. For self-reducible problems in NP, approximate counting reduces to approximate uniform sampling (Jerrum-Valiant-Vazirani) — TODO citation.

Notable problems

• Permanent of a 0-1 matrix: the seminal result of Valiant (1979) shows that computing the permanent $\mathrm{perm}(A)={\sum }_{\sigma \in S_n}{\prod }_i{A}_{i,\sigma (i)}$ is $\#P$-complete — TODO citation. The permanent counts the number of perfect matchings in a bipartite graph. This is in striking contrast to the determinant, which is computable in polynomial time.
• SAT: counting the number of satisfying assignments to a Boolean formula is $\#P$-complete.
• Perfect matchings: counting the perfect matchings of a general graph is $\#P$-complete.