Editing ♯P (section)

==Formal definitions==
'''#P''' is 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>x \in \{0,1\}^*</math>, <math>f(x)</math> equals the number of accepting branches in <math>M</math>'s computation graph on <math>x</math>.<ref name="Barak-Counting">{{cite web |last1=Barak |first1=Boaz |title=Complexity of counting |url=https://www.cs.princeton.edu/courses/archive/spring06/cos522/count.pdf |website=Computer Science 522: Computational Complexity |publisher=Princeton University |date=Spring 2006}}</ref> 

'''#P''' can also be equivalently defined in terms of a verifer. A decision problem is in '''[[NP (complexity)|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 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.<ref name="Barak-Counting"/> 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 [[deterministic Turing machine]] <math>V</math>, called the verifier, such that for every <math>x \in \{0,1\}^*</math>, <math>f(x)=\Big| \big \{y \in \{0,1\}^{p(|x|)} : V(x,y)=1 \big \} \Big| </math>.<ref>{{cite book |last1=Arora |first1=Sanjeev |last2=Barak|author1-link=Sanjeev Arora |first2=Boaz|author2-link=Boaz Barak |title=Computational Complexity: A Modern Approach |date=2009 |publisher=Cambridge University Press |isbn=978-0-521-42426-4|page=344}}</ref> (In other words, <math>f(x)</math> equals the size of the set containing all of the polynomial-size certificates).