In computational complexity theory, the complexity class #P (pronounced "sharp P" or, sometimes "number P" or "hash P") is the set of the counting problems associated with the decision problems in the set NP.
More formally, #P is the class of function problems of the form "compute f(x)", where f is the number of accepting paths of a nondeterministic Turing machine running in polynomial time.
An NP decision problem is often of the form "Are there any solutions that satisfy certain constraints?"
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.
The closest decision problem class to #P is PP, which asks whether a majority (more than half) of the computation paths accept.
The decision problem class ⊕P (pronounced "Parity-P") instead asks for the least significant bit of the #P answer.
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.
The class #P asks how many certificates there exist for a problem instance that can be checked for correctness in polynomial time.
[1] In this context, #P is defined as follows: 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.