Editing Complexity class (section)

===Counting problems===
{{Main|Counting problem (complexity)}}
A '''counting problem''' asks not only ''whether'' a solution exists (as with a [[decision problem]]), but asks ''how many'' solutions exist.{{snf|Fortnow|1997}} For example, the decision problem <math>\texttt{CYCLE}</math> asks ''whether'' a particular graph <math>G</math> has a [[simple cycle]] (the answer is a simple yes/no); the corresponding counting problem <math>\#\texttt{CYCLE}</math> (pronounced "sharp cycle") asks ''how many'' simple cycles <math>G</math> has.{{sfn|Arora|2003}} The output to a counting problem is thus a number, in contrast to the output for a decision problem, which is a simple yes/no (or accept/reject, 0/1, or other equivalent scheme).{{sfn|Arora|Barak|2009|p=342}}  

Thus, whereas decision problems are represented mathematically as [[formal language]]s, counting problems are represented mathematically as [[Function (mathematics)|functions]]: a counting problem is formalized as the function <math>f:\{0,1\}^* \to \mathbb{N}</math> such that for every input <math>w \in \{0,1\}^*</math>, <math>f(w)</math> is the number of solutions. For example, in the <math>\#\texttt{CYCLE}</math> problem, the input is a graph <math>G \in \{0,1\}^*</math> (a graph represented as a string of [[bit]]s) and <math>f(G)</math> is the number of simple cycles in <math>G</math>. 

Counting problems arise in a number of fields, including [[statistical estimation]], [[statistical physics]], [[network design]], and [[economics]].{{sfn|Arora|Barak|2009|p=341–342}}

==== 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>.