Editing Complexity class (section)

==== Important complexity classes ====
{{Main|♯P}}
'''#P''' (pronounced "sharp P") is an important class of counting problems that can be thought of as the counting version of '''NP'''.{{sfn|Barak|2006}} The connection to '''NP''' arises from the fact that the number of solutions to a problem equals the number of accepting branches in a [[nondeterministic Turing machine]]'s computation tree. '''#P''' is thus formally defined as follows:
: '''#P''' is the set of all functions <math>f:\{0,1\}^* \to \mathbb{N}</math> such that there is a polynomial time nondeterministic Turing machine <math>M</math> such that for all <math>w \in \{0,1\}^*</math>, <math>f(w)</math> equals the number of accepting branches in <math>M</math>'s computation tree on <math>w</math>.{{sfn|Barak|2006}} 

And just as '''NP''' can be defined both in terms of nondeterminism and in terms of a verifier (i.e. as an [[interactive proof system]]), so too can '''#P''' be equivalently defined in terms of a verifier. Recall that a decision problem is in '''NP''' if there exists a polynomial-time checkable [[certificate (complexity)|certificate]] to a given problem instance—that is, '''NP''' asks whether there exists a proof of membership (a certificate) for the input that can be checked for correctness in polynomial time. The class '''#P''' asks ''how many'' such certificates exist.{{sfn|Barak|2006}} In this context, '''#P''' is defined as follows:
: '''#P''' is the set of functions <math>f: \{0,1\}^* \to \mathbb{N}</math> such that there exists a polynomial <math>p: \mathbb{N} \to \mathbb{N}</math> and a polynomial-time Turing machine <math>V</math> (the verifier), such that for every <math>w \in \{0,1\}^*</math>, <math>f(w)=\Big| \big\{c \in \{0,1\}^{p(|w|)} : V(w,c)=1 \big\}\Big| </math>.{{sfn|Arora|Barak|2009|p=344}} In other words, <math>f(w)</math> equals the size of the set containing all of the polynomial-size certificates for <math>w</math>.