Editing Computational complexity theory (section)

===Separations between other complexity classes===
Many known complexity classes are suspected to be unequal, but this has not been proved. For instance <math>\textsf{P} \subseteq \textsf{NP} \subseteq \textsf{PP} \subseteq \textsf{PSPACE}</math>, but it is possible that <math>\textsf{P} = \textsf{PSPACE}</math>. If <math>\textsf{P}</math> is not equal to <math>\textsf{NP}</math>, then <math>\textsf{P}</math> is not equal to <math>\textsf{PSPACE}</math> either. Since there are many known complexity classes between <math>\textsf{P}</math> and <math>\textsf{PSPACE}</math>, such as <math>\textsf{RP}</math>, <math>\textsf{BPP}</math>, <math>\textsf{PP}</math>, <math>\textsf{BQP}</math>, <math>\textsf{MA}</math>, <math>\textsf{PH}</math>, etc., it is possible that all these complexity classes collapse to one class. Proving that any of these classes are unequal would be a major breakthrough in complexity theory.

Along the same lines, <math>\textsf{co-NP}</math> is the class containing the [[Complement (complexity)|complement]] problems (i.e. problems with the ''yes''/''no'' answers reversed) of <math>\textsf{NP}</math> problems. It is believed<ref>[http://www.cs.princeton.edu/courses/archive/spr06/cos522/ Boaz Barak's course on Computational Complexity] [http://www.cs.princeton.edu/courses/archive/spr06/cos522/lec2.pdf Lecture 2]</ref> that <math>\textsf{NP}</math> is not equal to <math>\textsf{co-NP}</math>; however, it has not yet been proven. It is clear that if these two complexity classes are not equal then <math>\textsf{P}</math> is not equal to <math>\textsf{NP}</math>, since <math>\textsf{P} = \textsf{co-P}</math>. Thus if <math>P = NP</math> we would have <math>\textsf{co-P} = \textsf{co-NP}</math> whence <math>\textsf{NP} = \textsf{P} = \textsf{co-P} = \textsf{co-NP}</math>.

Similarly, it is not known if <math>\textsf{L}</math> (the set of all problems that can be solved in logarithmic space) is strictly contained in <math>\textsf{P}</math> or equal to <math>\textsf{P}</math>. Again, there are many complexity classes between the two, such as <math>\textsf{NL}</math> and <math>\textsf{NC}</math>, and it is not known if they are distinct or equal classes.

It is suspected that <math>\textsf{P}</math> and <math>\textsf{BPP}</math> are equal. However, it is currently open if <math>\textsf{BPP} = \textsf{NEXP}</math>.