Editing Complexity class (section)

====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}}