Editing Complexity class (section)

===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)}}