Editing Complexity class (section)

==Other types of problems==
While most complexity classes studied by computer scientists are sets of [[decision problem]]s, there are also a number of complexity classes defined in terms of other types of problems. In particular, there are complexity classes consisting of [[counting problem (complexity)|counting problems]], [[function problem]]s, and [[promise problem]]s. These are explained in greater detail below.

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

===Function problems===
{{Main|Function problem}}
Counting problems are a subset of a broader class of problems called '''function problems'''. A function problem is a type of problem in which the values of a [[Function (mathematics)|function]] <math>f:A \to B</math> are computed. Formally, a function problem <math>f</math> is defined as a relation <math>R</math> over strings of an arbitrary [[Alphabet (formal languages)|alphabet]] <math>\Sigma</math>:
:<math> R \subseteq \Sigma^* \times \Sigma^*</math>
An algorithm solves <math>f</math> if for every input <math>x</math> such that there exists a <math>y</math> satisfying <math>(x, y) \in R</math>, the algorithm produces one such <math>y</math>. This is just another way of saying that <math>f</math> is a [[function (mathematics)|function]] and the algorithm solves <math>f(x)</math> for all <math>x \in \Sigma^*</math>.

====Important complexity classes====
An important function complexity class is '''[[FP (complexity)|FP]]''', the class of efficiently solvable functions.{{sfn|Arora|Barak|2009|p=344}} More specifically, '''FP''' is the set of function problems that can be solved by a [[deterministic Turing machine]] in [[polynomial time]].{{sfn|Arora|Barak|2009|p=344}} '''FP''' can be thought of as the function problem equivalent of '''[[P (complexity)|P]]'''. Importantly, '''FP''' provides some insight into both counting problems and [[P versus NP|'''P''' versus '''NP''']]. If '''#P'''='''FP''', then the functions that determine the number of certificates for problems in '''NP''' are efficiently solvable. And since computing the number of certificates is at least as hard as determining whether a certificate exists, it must follow that if '''#P'''='''FP''' then '''P'''='''NP''' (it is not known whether this holds in the reverse, i.e. whether '''P'''='''NP''' implies '''#P'''='''FP''').{{sfn|Arora|Barak|2009|p=344}}  

Just as '''FP''' is the function problem equivalent of '''P''', '''[[FNP (complexity)|FNP]]''' is the function problem equivalent of '''[[NP (complexity)|NP]]'''. Importantly, '''FP'''='''FNP''' if and only if '''P'''='''NP'''.{{sfn|Rich|2008|p=689 (510 in provided PDF)}}

===Promise problems===
{{Main|Promise problem}}
'''Promise problems''' are a generalization of decision problems in which the input to a problem is guaranteed ("promised") to be from a particular subset of all possible inputs. Recall that with a decision problem <math>L \subseteq \{0,1\}^*</math>, an algorithm <math>M</math> for <math>L</math> must act (correctly) on ''every'' <math>w \in \{0,1\}^*</math>. A promise problem loosens the input requirement on <math>M</math> by restricting the input to some subset of <math>\{0,1\}^*</math>. 

Specifically, a promise problem is defined as a pair of non-intersecting sets <math>(\Pi_{\text{ACCEPT}},\Pi_{\text{REJECT}})</math>, where:{{sfn|Watrous|2006|p=1}}
* <math>\Pi_{\text{ACCEPT}} \subseteq \{0,1\}^*</math> is the set of all inputs that are accepted.
* <math>\Pi_{\text{REJECT}} \subseteq \{0,1\}^*</math> is the set of all inputs that are rejected.

The input to an algorithm <math>M</math> for a promise problem <math>(\Pi_{\text{ACCEPT}},\Pi_{\text{REJECT}})</math> is thus <math>\Pi_{\text{ACCEPT}} \cup \Pi_{\text{REJECT}}</math>, which is called the '''promise'''. Strings in <math>\Pi_{\text{ACCEPT}} \cup \Pi_{\text{REJECT}}</math> are said to ''satisfy the promise''.{{sfn|Watrous|2006|p=1}} By definition, <math>\Pi_{\text{ACCEPT}}</math> and <math>\Pi_{\text{REJECT}}</math> must be disjoint, i.e. <math>\Pi_{\text{ACCEPT}} \cap \Pi_{\text{REJECT}} = \emptyset</math>. 

Within this formulation, it can be seen that decision problems are just the subset of promise problems with the trivial promise <math>\Pi_{\text{ACCEPT}} \cup \Pi_{\text{REJECT}} = \{0,1\}^*</math>. With decision problems it is thus simpler to simply define the problem as only <math>\Pi_{\text{ACCEPT}}</math> (with <math>\Pi_{\text{REJECT}}</math> implicitly being <math>\{0,1\}^* / \Pi_{\text{ACCEPT}}</math>), which throughout this page is denoted <math>L</math> to emphasize that <math>\Pi_{\text{ACCEPT}}=L</math> is a [[formal language]].

Promise problems make for a more natural formulation of many computational problems. For instance, a computational problem could be something like "given a [[planar graph]], determine whether or not..."{{sfn|Goldreich|2006|p=255 (2–3 in provided pdf)}} This is often stated as a decision problem, where it is assumed that there is some translation schema that takes ''every'' string <math>s \in \{0,1\}^*</math> to a planar graph. However, it is more straightforward to define this as a promise problem in which the input is promised to be a planar graph.

====Relation to complexity classes====
Promise problems provide an alternate definition for standard complexity classes of decision problems. '''P''', for instance, can be defined as a promise problem:{{sfn|Goldreich|2006|p=257 (4 in provided pdf)}}
: '''P''' is the class of promise problems that are solvable in deterministic polynomial time. That is, the promise problem <math>(\Pi_{\text{ACCEPT}},\Pi_{\text{REJECT}})</math> is in '''P''' if there exists a polynomial-time algorithm <math>M</math> such that:
:* For every <math>x \in \Pi_{\text{ACCEPT}}, M(x)=1</math>
:* For ever <math>x \in \Pi_{\text{REJECT}}, M(x)=0</math>

Classes of decision problems—that is, classes of problems defined as formal languages—thus translate naturally to promise problems, where a language <math>L</math> in the class is simply <math>L= \Pi_{\text{ACCEPT}}</math> and <math>\Pi_{\text{REJECT}}</math> is implicitly <math>\{0,1\}^* / \Pi_{\text{ACCEPT}}</math>.

Formulating many basic complexity classes like '''P''' as promise problems provides little additional insight into their nature. However, there are some complexity classes for which formulating them as promise problems have been useful to computer scientists. Promise problems have, for instance, played a key role in the study of '''SZK''' (statistical zero-knowledge).{{sfn|Goldreich|2006|p=266 (11–12 in provided pdf)}}