Content deleted Content added
m →BQP: merge <math> |
Citation bot (talk | contribs) Alter: template type. | Use this bot. Report bugs. | Suggested by AManWithNoPlan | #UCB_webform 664/1682 |
||
Line 15:
== Overview of complexity classes ==
Some important complexity classes are P, BPP, BQP, PP, and P-Space. To define these we first define a promise problem. A promise problem is a decision problem which has an input assumed to be selected from the set of all possible input strings. A promise problem is a pair <math>A=(A_\text{yes},A_\text{no})</math>. <math>A_\text{yes}</math> is the set of yes instances, <math>A_\text{no}</math> is the set of no instances, and the intersection of these sets is such that <math>A_\text{yes} \cap A_\text{no} = \varnothing</math>. All of the previous complexity classes contain promise problems.<ref name=":27">{{cite
{| class="wikitable"
|+
| |||