Editing Complexity class (section)

==Basic complexity classes==
{{See also|List of complexity classes}}

===Basic definitions===
Complexity classes are often defined using granular sets of complexity classes called '''DTIME''' and '''NTIME''' (for time complexity) and '''DSPACE''' and '''NSPACE''' (for space complexity). Using [[big O notation]], they are defined as follows:
* The time complexity class <math>\mathsf{DTIME}(t(n))</math> is the set of all problems that are decided by an <math>O(t(n))</math> time deterministic Turing machine.
* The time complexity class <math>\mathsf{NTIME}(t(n))</math> is the set of all problems that are decided by an <math>O(t(n))</math> time nondeterministic Turing machine.
* The space complexity class <math>\mathsf{DSPACE}(s(n))</math> is the set of all problems that are decided by an <math>O(s(n))</math> space deterministic Turing machine.
* The space complexity class <math>\mathsf{NSPACE}(s(n))</math> is the set of all problems that are decided by an <math>O(s(n))</math> space nondeterministic Turing machine.

===Time complexity classes===
{{Main|Time complexity}}

====P and NP====
{{Main|P (complexity)|NP (complexity)}}
'''P''' is the class of problems that are solvable by a [[deterministic Turing machine]] in [[polynomial time]] and '''NP''' is the class of problems that are solvable by a [[nondeterministic Turing machine]] in polynomial time. Or more formally,
: <math>\mathsf{P} = \bigcup_{k\in\mathbb{N}} \mathsf{DTIME}(n^k) </math>
: <math>\mathsf{NP} = \bigcup_{k\in\mathbb{N}} \mathsf{NTIME}(n^k) </math>

'''P''' is often said to be the class of problems that can be solved "quickly" or "efficiently" by a deterministic computer, since the [[time complexity]] of solving a problem in '''P''' increases relatively slowly with the input size.

An important characteristic of the class '''NP''' is that it can be equivalently defined as the class of problems whose solutions are ''verifiable'' by a deterministic Turing machine in polynomial time. That is, a language is in '''NP''' if there exists a ''deterministic'' polynomial time Turing machine, referred to as the verifier, that takes as input a string <math>w</math> ''and'' a polynomial-size [[Certificate (complexity)|certificate]] string <math>c</math>, and accepts <math>w</math> if <math>w</math> is in the language and rejects <math>w</math> if <math>w</math> is not in the language. Intuitively, the certificate acts as a [[Mathematical proof|proof]] that the input <math>w</math> is in the language. Formally:{{sfn|Aaronson|2017|p=12}}
: '''NP''' is the class of languages <math>L</math> for which there exists a polynomial-time deterministic Turing machine <math>M</math> and a polynomial <math>p</math> such that for all <math>w \in \{0,1\}^*</math>, <math>w</math> is in <math>L</math> ''if and only if'' there exists some <math>c \in \{0,1\}^{p(|w|)}</math> such that <math>M(w,c)</math> accepts.

This equivalence between the nondeterministic definition and the verifier definition highlights a fundamental connection between [[Nondeterministic algorithm|nondeterminism]] and solution verifiability. Furthermore, it also provides a useful method for proving that a language is in '''NP'''—simply identify a suitable certificate and show that it can be verified in polynomial time.

=====The P versus NP problem=====
While there might seem to be an obvious difference between the class of problems that are efficiently solvable and the class of problems whose solutions are merely efficiently checkable, '''P''' and '''NP''' are actually at the center of one of the most famous unsolved problems in computer science: the [[P versus NP|'''P''' versus '''NP''']] problem. While it is known that <math>\mathsf{P} \subseteq \mathsf{NP}</math> (intuitively, deterministic Turing machines are just a subclass of nondeterministic Turing machines that don't make use of their nondeterminism; or under the verifier definition, '''P''' is the class of problems whose polynomial time verifiers need only receive the empty string as their certificate), it is not known whether '''NP''' is strictly larger than '''P'''. If '''P'''='''NP''', then it follows that nondeterminism provides ''no additional computational power'' over determinism with regards to the ability to quickly find a solution to a problem; that is, being able to explore ''all possible branches'' of computation provides ''at most'' a polynomial speedup over being able to explore only a single branch. Furthermore, it would follow that if there exists a proof for a problem instance and that proof can be quickly be checked for correctness (that is, if the problem is in '''NP'''), then there also exists an algorithm that can quickly ''construct'' that proof (that is, the problem is in '''P''').{{sfn|Aaronson|2017|p=3}} However, the overwhelming majority of computer scientists believe that <math>\mathsf{P}\neq\mathsf{NP}</math>,{{sfn|Gasarch|2019}} and most [[Cryptography#Modern cryptography|cryptographic schemes]] employed today rely on the assumption that <math>\mathsf{P}\neq\mathsf{NP}</math>.{{sfn|Aaronson|2017|p=4}}

====EXPTIME and NEXPTIME====
{{Main|EXPTIME|NEXPTIME}}
'''EXPTIME''' (sometimes shortened to '''EXP''') is the class of decision problems solvable by a deterministic Turing machine in exponential time and '''NEXPTIME''' (sometimes shortened to '''NEXP''') is the class of decision problems solvable by a nondeterministic Turing machine in exponential time. Or more formally,
: <math>\mathsf{EXPTIME} = \bigcup_{k\in\mathbb{N}} \mathsf{DTIME}(2^{n^k}) </math>
: <math>\mathsf{NEXPTIME} = \bigcup_{k\in\mathbb{N}} \mathsf{NTIME}(2^{n^k}) </math>

'''EXPTIME''' is a strict superset of '''P''' and '''NEXPTIME''' is a strict superset of '''NP'''. It is further the case that '''EXPTIME'''<math>\subseteq</math>'''NEXPTIME'''. It is not known whether this is proper, but if '''P'''='''NP''' then '''EXPTIME''' must equal '''NEXPTIME'''.

===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'''.