Editing Complexity class (section)

===Space complexity classes===
{{Main|Space complexity}}

====L and NL====
{{Main|L (complexity)|NL (complexity)}}
While it is possible to define [[Logarithmic growth|logarithmic]] time complexity classes, these are extremely narrow classes as sublinear times do not even enable a Turing machine to read the entire input (because <math>\log n < n </math>).{{efn|While a logarithmic runtime of <math>c \log n</math>, i.e. <math>\log n</math> multiplied by a constant <math>c</math>, allows a Turing machine to read inputs of size <math>n < c \log n</math>, there will invariably reach a point where <math>n > c \log n </math>.}}{{sfn|Sipser|2006|p=320}} However, there are a meaningful number of problems that can be solved in logarithmic space. The definitions of these classes require a [[multitape Turing machine|two-tape Turing machine]] so that it is possible for the machine to store the entire input (it can be shown that in terms of [[computability]] the two-tape Turing machine is equivalent to the single-tape Turing machine).{{sfn|Sipser|2006|p=321}} In the two-tape Turing machine model, one tape is the input tape, which is read-only. The other is the work tape, which allows both reading and writing and is the tape on which the Turing machine performs computations. The space complexity of the Turing machine is measured as the number of cells that are used on the work tape.

'''L''' (sometimes lengthened to '''LOGSPACE''') is then defined as the class of problems solvable in logarithmic space on a deterministic Turing machine and '''NL''' (sometimes lengthened to '''NLOGSPACE''') is the class of problems solvable in logarithmic space on a nondeterministic Turing machine. Or more formally,{{sfn|Sipser|2006|p=321}}
:<math>\mathsf{L} = \mathsf{DSPACE}(\log n)</math>
:<math>\mathsf{NL} = \mathsf{NSPACE}(\log n)</math>

It is known that <math>\mathsf{L}\subseteq\mathsf{NL}\subseteq\mathsf{P}</math>. However, it is not known whether any of these relationships is proper.

====PSPACE and NPSPACE====
{{Main|PSPACE (complexity)}}
The complexity classes '''PSPACE''' and '''NPSPACE''' are the space analogues to '''[[P (complexity) | P]]''' and '''[[NP (complexity) | NP]]'''. That is, '''PSPACE''' is the class of problems solvable in polynomial space by a deterministic Turing machine and '''NPSPACE''' is the class of problems solvable in polynomial space by a nondeterministic Turing machine. More formally,
:<math>\mathsf{PSPACE} = \bigcup_{k\in\mathbb{N}} \mathsf{DSPACE}(n^k)</math>
:<math>\mathsf{NPSPACE} = \bigcup_{k\in\mathbb{N}} \mathsf{NSPACE}(n^k)</math>

While it is not known whether '''P'''='''NP''', [[Savitch's theorem ]] famously showed that '''PSPACE'''='''NPSPACE'''. It is also known that <math>\mathsf{P} \subseteq \mathsf{PSPACE}</math>, which follows intuitively from the fact that, since writing to a cell on a Turing machine's tape is defined as taking one unit of time, a Turing machine operating in polynomial time can only write to polynomially many cells. It is suspected that '''P''' is strictly smaller than '''PSPACE''', but this has not been proven.

====EXPSPACE and NEXPSPACE====
{{Main article|EXPSPACE}}
The complexity classes '''EXPSPACE''' and '''NEXPSPACE''' are the space analogues to '''[[EXPTIME]]''' and '''[[NEXPTIME]]'''. That is, '''EXPSPACE''' is the class of problems solvable in exponential space by a deterministic Turing machine and '''NEXPSPACE''' is the class of problems solvable in exponential space by a nondeterministic Turing machine. Or more formally,
:<math>\mathsf{EXPSPACE} = \bigcup_{k\in\mathbb{N}} \mathsf{DSPACE}(2^{n^k})</math>
:<math>\mathsf{NEXPSPACE} = \bigcup_{k\in\mathbb{N}} \mathsf{NSPACE}(2^{n^k})</math>

[[Savitch's theorem]] showed that '''EXPSPACE'''='''NEXPSPACE'''. This class is extremely broad: it is known to be a strict superset of '''PSPACE''', '''NP''', and '''P''', and is believed to be a strict superset of '''EXPTIME'''.