Editing Complexity class (section)

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