Editing Computational complexity theory (section)

===Important complexity classes===

[[File:Complexity subsets pspace.svg|thumb|right|A representation of the relation among complexity classes; L would be another step "inside" NL]]
Many important complexity classes can be defined by bounding the time or space used by the algorithm. Some important complexity classes of decision problems defined in this manner are the following:

{| class="wikitable sortable"
! scope=col | Resource
! scope=col | <abbr title="of Turing Machine used to Model Computation">Determinism</abbr>
! scope=col | Complexity class
! scope=col | Resource constraint
|-
! scope=rowgroup rowspan=8 style="text-align:center;" | Space
! scope=rowgroup rowspan=4 style="text-align:center;" | Non-Deterministic
| [[NSPACE]](<math>f(n)</math>)
| data-sort-value=0 | <math>O(f(n))</math>
|-
| [[NL (complexity)|NL]]
| data-sort-value=1 | <math>O(\log n)</math>
|-
| [[NPSPACE]]
| data-sort-value=2 | <math>O(\text{poly}(n))</math>
|-
| [[NEXPSPACE]]
| data-sort-value=4 | <math>O(2^{\text{poly}(n)})</math>
|-
! scope=rowgroup rowspan=4 style="text-align:center;" | Deterministic
| [[DSPACE]](<math>f(n)</math>)
| data-sort-value=0 | <math>O(f(n))</math>
|-
| [[L (complexity)|L]]
| data-sort-value=1 | <math>O(\log n)</math>
|-
| [[PSPACE]]
| data-sort-value=2 | <math>O(\text{poly}(n))</math>
|-
| [[EXPSPACE]]
| data-sort-value=4 | <math>O(2^{\text{poly}(n)})</math>
|-
! scope=rowgroup rowspan=6 style="text-align:center;" | Time
! scope=rowgroup rowspan=3 style="text-align:center;" | Non-Deterministic
| [[NTIME]](<math>f(n)</math>)
| data-sort-value=0 | <math>O(f(n))</math>
|-
| [[NP (complexity)|NP]]
| data-sort-value=2 | <math>O(\text{poly}(n))</math>
|-
| [[NEXPTIME]]
| data-sort-value=4 | <math>O(2^{\text{poly}(n)})</math>
|-
! scope=rowgroup rowspan=3 style="text-align:center;" | Deterministic
| [[DTIME]](<math>f(n)</math>)
| data-sort-value=0 | <math>O(f(n))</math>
|-
| [[P (complexity)|P]]
| data-sort-value=2 | <math>O(\text{poly}(n))</math>
|-
| [[EXPTIME]]
| data-sort-value=4 | <math>O(2^{\text{poly}(n)})</math>
|}

Logarithmic-space classes do not account for the space required to represent the problem.

It turns out that PSPACE = NPSPACE and EXPSPACE = NEXPSPACE by [[Savitch's theorem]].

Other important complexity classes include [[BPP (complexity)|BPP]], [[ZPP (complexity)|ZPP]] and [[RP (complexity)|RP]], which are defined using [[probabilistic Turing machine]]s; [[AC (complexity)|AC]] and [[NC (complexity)|NC]], which are defined using Boolean circuits; and [[BQP]] and [[QMA]], which are defined using quantum Turing machines. [[Sharp-P|#P]] is an important complexity class of counting problems (not decision problems). Classes like [[IP (complexity)|IP]] and [[AM (complexity)|AM]] are defined using [[Interactive proof system]]s. [[ALL (complexity)|ALL]] is the class of all decision problems.