Editing NP (complexity) (section)

{{short description|Complexity class used to classify decision problems}}
{{more footnotes|date=October 2015}}
{{unsolved|computer science|<math>\mathsf{P\ \overset{?}{=}\ NP}</math><!-- as of 2022, \overset destroys binary-operator spacings, so they are added here manually -->}}
[[File:P np np-complete np-hard.svg|thumb|300px|right|[[Euler diagram]] for [[P (complexity)|P]], NP, [[NP-complete]], and [[NP-hard]] set of problems. Under the assumption that P&nbsp;≠&nbsp;NP, the existence of problems within NP but outside both '''P''' and NP-complete was [[Ladner's theorem|established by Ladner]].<ref>{{cite journal |first=R. E. |last=Ladner |title=On the structure of polynomial time reducibility |journal=J. ACM |volume=22 |pages=151&ndash;171 |doi=10.1145/321864.321877 |year=1975 |s2cid=14352974 |doi-access=free }} Corollary 1.1.</ref>]]

In [[computational complexity theory]], '''NP''' ('''nondeterministic polynomial time''') is a [[complexity class]] used to classify [[decision problem]]s.  NP is the [[Set (mathematics)|set]] of decision problems for which the [[Computational complexity theory#Problem instances|problem instances]], where the answer is "yes", have [[mathematical proof|proofs]] verifiable in [[polynomial time]] by a [[deterministic Turing machine]], or alternatively the set of problems that can be solved in polynomial time by a [[nondeterministic Turing machine]].<ref name = "kleinberg2006">{{cite book |year=2006 |edition=2nd |title=Algorithm Design |url=https://archive.org/details/algorithmdesign0000klei |url-access=registration |first1=Jon |last1=Kleinberg |first2=Éva |last2=Tardos |isbn=0-321-37291-3 |publisher=Addison-Wesley |page=[https://archive.org/details/algorithmdesign0000klei/page/464 464]}}</ref><ref group="Note">''Polynomial time'' refers to how quickly the number of operations needed by an algorithm, relative to the size of the problem, grows. It is therefore a measure of efficiency of an algorithm.</ref>

* NP is the set of decision problems ''solvable'' in polynomial time by a [[nondeterministic Turing machine]].
* NP is the set of decision problems ''verifiable'' in polynomial time by a [[deterministic Turing machine]].

The first definition is the basis for the abbreviation NP; "[[Nondeterministic algorithm|nondeterministic]], polynomial time". These two definitions are equivalent because the algorithm based on the Turing machine consists of two phases, the first of which consists of a guess about the solution, which is generated in a nondeterministic way, while the second phase consists of a deterministic algorithm that verifies whether the guess is a solution to the problem.<ref>Alsuwaiyel, M. H.: ''Algorithms: Design Techniques and Analysis'', [https://books.google.com/books?id=SPx4iHZEOugC&pg=PA283 p.&nbsp;283].</ref>

The complexity class [[P (complexity)|P]] (all problems solvable, deterministically, in polynomial time) is contained in NP (problems where solutions can be verified in polynomial time), because if a problem is solvable in polynomial time, then a solution is also verifiable in polynomial time by simply solving the problem. It is widely believed, but not proven, that [[P versus NP problem|P is smaller than NP]], in other words, that decision problems exist that cannot be solved in polynomial time even though their solutions can be checked in polynomial time. The hardest problems in NP are called [[NP-complete]] problems. An algorithm solving such a problem in polynomial time is also able to solve any other NP problem in polynomial time. If P were in fact equal to NP, then a polynomial-time algorithm would exist for solving NP-complete, and by corollary, all NP problems.<ref name="poll">{{cite journal |author=William Gasarch |author-link=William Gasarch |title=The P=?NP poll |journal=SIGACT News |volume=33 |issue=2 |pages=34–47 |date=June 2002 |url=https://www.cs.umd.edu/~gasarch/papers/poll.pdf |doi=10.1145/1052796.1052804 |s2cid=18759797 |access-date=2008-12-29}}</ref>

The complexity class NP is related to the complexity class [[co-NP]], for which the answer "no" can be verified in polynomial time. Whether or not {{nobr|NP {{=}} co-NP}} is another outstanding question in complexity theory.<ref name = "kleinberg2006p496">{{cite book |year=2006 |edition=2nd |title=Algorithm Design |url=https://archive.org/details/algorithmdesign0000klei |url-access=registration |first1=Jon |last1=Kleinberg |first2=Éva |last2=Tardos |isbn=0-321-37291-3 |page=[https://archive.org/details/algorithmdesign0000klei/page/496 496]|publisher=Pearson/Addison-Wesley }}</ref>