♯P

Related complexity classes

Clearly, a #P problem must be at least as hard as the corresponding NP problem. If it's easy to count answers, then it must be easy to tell whether there are any answers—just count them and see whether the count is greater than zero. Some of these problems, such as root counting, are easy enough to be in FP, while others are #P-complete.

One consequence of Toda's theorem is that a polynomial-time machine with a #P oracle (P^#P) can solve all problems in PH, the entire polynomial hierarchy. In fact, the polynomial-time machine only needs to make one #P query to solve any problem in PH. This is an indication of the extreme difficulty of solving #P-complete problems exactly.

Surprisingly, some #P problems that are believed to be difficult correspond to easy (for example linear-time) P problems. For more information on this, see #P-complete.

The closest decision problem class to #P is PP, which asks whether a majority (more than half) of the computation paths accept. This finds the most significant bit in the #P problem answer. The decision problem class ⊕P (pronounced "Parity-P") instead asks for the least significant bit of the #P answer.

Formal definitions

#P is formally defined as follows:

#P is the set of all functions ${\displaystyle f:\{0,1{\}}^{\ast }\to \mathbb{N}}$ such that there is a polynomial-time nondeterministic Turing machine ${\displaystyle M}$ such that for all ${\displaystyle x\in \{0,1{\}}^{\ast }}$, ${\displaystyle f(x)}$ equals the number of accepting branches in ${\displaystyle M}$'s computation graph on ${\displaystyle x}$.

#P can also be equivalently defined in terms of a verifer. A decision problem is in NP if there exists a polynomial-time checkable certificate to a given problem instance—that is, NP asks whether there exists a proof of membership for the input that can be checked for correctness in polynomial time. Questions in #P ask how many certificates there exist for a problem instance that can be checked for correctness in polynomial time. In this context, #P is defined as follows:

#P is the set of functions ${\displaystyle f:\{0,1{\}}^{\ast }\to \mathbb{N}}$ such that there exists a polynomial ${\displaystyle p:\mathbb{N}\to \mathbb{N}}$ and a polynomial-time deterministic Turing machine ${\displaystyle V}$, called the verifier, such that for every ${\displaystyle x\in \{0,1{\}}^{\ast }}$, ${\displaystyle f(x)=|\{y\in \{0,1{\}}^{p(|x|)}:V(x,y)=1\}|}$. (In other words, ${\displaystyle f(x)}$ equals the size of the set containing all of the polynomial-size certificates).

History

The complexity class #P was first defined by Leslie Valiant in a 1979 article on the computation of the permanent of a square matrix, in which he proved that permanent is #P-complete.

Larry Stockmeyer has proved that for every #P problem ${\displaystyle P}$ there exists a randomized algorithm using an oracle for SAT, which given an instance ${\displaystyle a}$ of ${\displaystyle P}$ and ${\displaystyle ϵ>0}$ returns with high probability a number ${\displaystyle x}$ such that ${\displaystyle (1-ϵ)P(a)\le x\le (1+ϵ)P(a)}$. The runtime of the algorithm is polynomial in ${\displaystyle a}$ and ${\displaystyle 1/ϵ}$. The algorithm is based on the leftover hash lemma.