Editing Complexity class (section)

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