♯P
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.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.