Editing ♯P (section)

==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 finding]], are easy enough to be in [[FP (complexity)|FP]], while others are [[♯P-complete|#P-complete]].

One consequence of [[Toda's theorem]] is that a [[Time complexity#Polynomial time|polynomial-time]] machine with a '''#P''' [[oracle machine|oracle]] ('''P'''<sup>'''#P'''</sup>) can solve all problems in '''[[PH (complexity)|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 (complexity)|P]]''' problems.  For more information on this, see [[sharp-P-complete|#P-complete]].

The closest decision problem class to '''#P''' is '''[[PP (complexity)|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 '''[[Parity P|⊕P]]''' (pronounced "Parity-P") instead asks for the least significant bit of the '''#P''' answer.