View source for NP (complexity)

{{short description|Complexity class used to classify decision problems}}
{{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|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 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|computational complexity theory]], '''NP''' ('''nondeterministic polynomial time''') is a [[Complexity class|complexity class]] used to classify [[Decision problem|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|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|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>

It is easy to see that 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. But NP contains many more problems,<ref group="Note">Under the assumption that P&nbsp;≠&nbsp;NP.</ref> the hardest of which 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. The most important [[P versus NP problem|P versus NP (“P&nbsp;=&nbsp;NP?”) problem]], asks whether polynomial-time algorithms exist for solving NP-complete, and by corollary, all NP problems. It is widely believed that this is not the case.<ref name="poll">{{cite journal |author=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|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]}}</ref>

== Formal definition ==
The complexity class NP can be defined in terms of [[NTIME]] as follows:

: <math>\mathsf{NP} = \bigcup_{k\in\mathbb{N}} \mathsf{NTIME}(n^k),</math>

where <math>\mathsf{NTIME}(n^k)</math> is the set of decision problems that can be solved by a [[Nondeterministic Turing machine|nondeterministic Turing machine]] in <math>O(n^k)</math> time.

Alternatively, NP can be defined using deterministic Turing machines as verifiers. A [[Formal language|language]] ''L'' is in NP if and only if there exist polynomials ''p'' and ''q'', and a deterministic Turing machine ''M'', such that
* For all ''x'' and ''y'', the machine ''M'' runs in time ''p''(|''x''|) on input {{tmath|1=(x,y)}}.
* For all ''x'' in ''L'', there exists a string ''y'' of length ''q''(|''x''|) such that {{tmath|1=M(x, y) = 1}}.
* For all ''x'' not in ''L'' and all strings ''y'' of length ''q''(|''x''|), {{tmath|1=M(x, y) = 0}}.

== Background ==
Many [[Computer science|computer science]] problems are contained in NP, like decision versions of many [[Search problem|search]] and optimization problems.

=== Verifier-based definition ===
In order to explain the verifier-based definition of NP, consider the [[Subset sum problem|subset sum problem]]:
Assume that we are given some [[Integer|integer]]s, {−7, −3, −2, 5, 8}, and we wish to know whether some of these integers sum up to zero. Here the answer is "yes", since the integers {−3, −2, 5} corresponds to the sum {{nowrap|(−3) + (−2) + 5 {{=}} 0.}} 

To answer whether some of the integers add to zero we can create an algorithm that obtains all the possible subsets. As the number of integers that we feed into the algorithm becomes larger, both the number of subsets and the computation time grows exponentially.

But notice that if we are given a particular subset, we can ''efficiently verify'' whether the subset sum is zero, by summing the integers of the subset. If the sum is zero, that subset is a ''proof'' or [[Witness (mathematics)|witness]] for the answer is "yes". An algorithm that verifies whether a given subset has sum zero is a ''verifier''. Clearly, summing the integers of a subset can be done in polynomial time, and the subset sum problem is therefore in NP.

The above example can be generalized for any decision problem. Given any instance I of problem <math> \Pi </math> and witness W, if there exists a ''verifier'' V so that given the ordered pair (I,&nbsp;W) as input, V returns "yes" in polynomial time if the witness proves that the answer is "yes" or "no" in polynomial time otherwise, then <math> \Pi </math> is in NP.

The "no"-answer version of this problem is stated as: "given a finite set of integers, does every non-empty subset have a nonzero sum?". The verifier-based definition of NP does ''not'' require an efficient verifier for the "no"-answers. The class of problems with such verifiers for the "no"-answers is called co-NP. In fact, it is an open question whether all problems in NP also have verifiers for the "no"-answers and thus are in co-NP.

In some literature the verifier is called the "certifier", and the witness the "[[Certificate (complexity)|certificate]]".<ref name = "kleinberg2006"/>

=== Machine-definition ===
Equivalent to the verifier-based definition is the following characterization: NP is the class of [[Decision problem|decision problem]]s solvable by a [[Nondeterministic Turing machine|nondeterministic Turing machine]] that runs in polynomial time. That is to say, a decision problem <math> \Pi </math> is in NP whenever <math> \Pi </math> is recognized by some polynomial-time nondeterministic Turing machine <math> M </math> with an '''existential acceptance condition''', meaning that <math> w \in \Pi </math> if and only if some computation path of <math> M(w) </math> leads to an accepting state. This definition is equivalent to the verifier-based definition because a nondeterministic Turing machine could solve an NP problem in polynomial time by nondeterministically selecting a certificate and running the verifier on the certificate.  Similarly, if such a machine exists, then a polynomial time verifier can naturally be constructed from it.

In this light, we can define co-NP dually as the class of decision problems recognizable by polynomial-time nondeterministic Turing machines with an existential rejection condition.  Since an existential rejection condition is exactly the same thing as a '''universal acceptance condition''', we can understand the ''NP vs. co-NP'' question as asking whether the existential and universal acceptance conditions have the same expressive power for the class of polynomial-time nondeterministic Turing machines.

== Properties ==
NP is closed under [[Union (set theory)|union]], [[Intersection|intersection]], [[Concatenation|concatenation]], [[Kleene star]] and [[Formal language#Operations on languages|reversal]]. It is not known whether NP is closed under [[Complement (set theory)|complement]] (this question is the so-called "NP versus co-NP" question).

== Why some NP problems are hard to solve ==
Because of the many important problems in this class, there have been extensive efforts to find polynomial-time algorithms for problems in NP. However, there remain a large number of problems in NP that defy such attempts, seeming to require super-polynomial time. Whether these problems are not decidable in polynomial time is one of the greatest open questions in [[Computer science|computer science]] (see [[P versus NP problem|'''P''' versus NP ("P&nbsp;=&nbsp;NP") problem]] for an in-depth discussion).

An important notion in this context is the set of NP-complete decision problems, which is a subset of NP and might be informally described as the "hardest" problems in NP. If there is a polynomial-time algorithm for even ''one'' of them, then there is a polynomial-time algorithm for ''all'' the problems in NP. Because of this, and because dedicated research has failed to find a polynomial algorithm for any NP-complete problem, once a problem has been proven to be NP-complete, this is widely regarded as a sign that a polynomial algorithm for this problem is unlikely to exist.

However, in practical uses, instead of spending computational resources looking for an optimal solution, a good enough (but potentially suboptimal) solution may often be found in polynomial time. Also, the real-life applications of some problems are easier than their theoretical equivalents.

== Equivalence of definitions ==
The two definitions of NP as the class of problems solvable by a nondeterministic [[Turing machine]] (TM) in polynomial time and the class of problems verifiable by a deterministic Turing machine in polynomial time are equivalent. The proof is described by many textbooks, for example, Sipser's ''Introduction to the Theory of Computation'', section 7.3.

To show this, first, suppose we have a deterministic verifier. A non-deterministic machine can simply nondeterministically run the verifier on all possible proof strings (this requires only polynomially many steps because it can nondeterministically choose the next character in the proof string in each step, and the length of the proof string must be polynomially bounded). If any proof is valid, some path will accept; if no proof is valid, the string is not in the language and it will reject.

Conversely, suppose we have a non-deterministic TM called A accepting a given language L. At each of its polynomially many steps, the machine's [[Computation tree|computation tree]] branches in at most a finite number of directions. There must be at least one accepting path, and the string describing this path is the proof supplied to the verifier. The verifier can then deterministically simulate A, following only the accepting path, and verifying that it accepts at the end. If A rejects the input, there is no accepting path, and the verifier will always reject.

== Relationship to other classes ==
[[Image:Complexity subsets pspace.svg|300px|thumb|right|A representation of the relation among complexity classes]]
[[Image:Complexity-classes-polynomial.svg|thumb|Inclusions of complexity classes including [[P (complexity)|P]], [[NP (complexity)|NP]], [[Co-NP|co-NP]], [[BPP (complexity)|BPP]], P/poly, [[PH (complexity)|PH]], and [[PSPACE|PSPACE]]]]
NP contains all problems in [[P (complexity)|P]], since one can verify any instance of the problem by simply ignoring the proof and solving it. NP is contained in [[PSPACE]]—to show this, it suffices to construct a PSPACE machine that loops over all proof strings and feeds each one to a polynomial-time verifier. Since a polynomial-time machine can only read polynomially many bits, it cannot use more than polynomial space, nor can it read a proof string occupying more than polynomial space (so we do not have to consider proofs longer than this). NP is also contained in [[EXPTIME]], since the same algorithm operates in exponential time.

co-NP contains those problems that have a simple proof for ''no'' instances, sometimes called counterexamples. For example, [[Primality test|primality test]]ing trivially lies in co-NP, since one can refute the primality of an integer by merely supplying a nontrivial factor. NP and co-NP together form the first level in the [[Polynomial hierarchy|polynomial hierarchy]], higher only than P.

NP is defined using only deterministic machines. If we permit the verifier to be probabilistic (this, however, is not necessarily a BPP machine<ref>{{cite web |url=https://complexityzoo.uwaterloo.ca/Complexity_Zoo:E#existsbpp |title=Complexity Zoo:E  |website=Complexity Zoo |access-date=23 March 2018 |archive-url=https://web.archive.org/web/20201111211915/https://complexityzoo.uwaterloo.ca/Complexity_Zoo:E |archive-date=2020-11-11 |url-status=dead}}</ref>), we get the class '''MA''' solvable using an [[Arthur–Merlin protocol]] with no communication from Arthur to Merlin.

The relationship between '''[[BPP (complexity)|BPP]]''' and '''NP''' is unknown: it is not known whether '''BPP''' is a [[Subset|subset]] of '''NP''', '''NP''' is a subset of '''BPP''' or neither. If '''NP''' is contained in '''BPP''', which is considered unlikely since it would imply practical solutions for NP-complete problems, then '''NP''' = '''RP''' and '''[[PH (complexity)|PH]]''' ⊆ '''BPP'''.<ref>Lance Fortnow, [http://weblog.fortnow.com/2005/12/pulling-out-quantumness.html Pulling Out The Quantumness],  December 20, 2005</ref>

NP is a class of [[Decision problem|decision problem]]s; the analogous class of function problems is [[FNP (complexity)|FNP]].

The only known strict inclusions come from the [[Time hierarchy theorem|time hierarchy theorem]] and the [[Space hierarchy theorem|space hierarchy theorem]], and respectively they are <math>\mathsf{NP \subsetneq NEXPTIME}</math> and <math>\mathsf{NP \subsetneq EXPSPACE}</math>.

== Other characterizations ==
In terms of [[Descriptive complexity theory|descriptive complexity theory]], NP corresponds precisely to the set of languages definable by existential [[Philosophy:Second-order logic|second-order logic]] ([[Fagin's theorem]]).

NP can be seen as a very simple type of [[Interactive proof system|interactive proof system]], where the prover comes up with the proof certificate and the verifier is a deterministic polynomial-time machine that checks it. It is complete because the right proof string will make it accept if there is one, and it is sound because the verifier cannot accept if there is no acceptable proof string.

A major result of complexity theory is that NP can be characterized as the problems solvable by [[Probabilistically checkable proof|probabilistically checkable proof]]s where the verifier uses O(log ''n'') random bits and examines only a constant number of bits of the proof string (the class '''PCP'''(log ''n'', 1)). More informally, this means that the NP verifier described above can be replaced with one that just "spot-checks" a few places in the proof string, and using a limited number of coin flips can determine the correct answer with high probability. This allows several results about the hardness of [[Approximation algorithm|approximation algorithm]]s to be proven.

== Examples ==

=== P ===

All problems in [[P (complexity)|P]], denoted <math>\mathsf{P \subseteq NP}</math>. Given a certificate for a problem in '''P''', we can ignore the certificate and just solve the problem in polynomial time.

=== Integer factorization ===

The decision problem version of the integer factorization problem: given integers ''n'' and ''k'', is there a factor ''f'' with 1 < ''f'' < ''k'' and ''f'' dividing ''n''?<ref name=":0" />

=== NP-complete problems ===

{{main|List of NP-complete problems}}

Every [[NP-completeness|NP-complete]] problem is in NP.

==== Boolean satisfiability ====

The [[Boolean satisfiability problem]] ('''SAT'''), where we want to know whether or not a certain formula in propositional logic with Boolean variables is true for some value of the variables.<ref>{{Cite book|last=Karp|first=Richard|title=Complexity of Computer Computations |chapter=Reducibility among Combinatorial Problems |date=1972|chapter-url=http://cgi.di.uoa.gr/~sgk/teaching/grad/handouts/karp.pdf|pages=85–103 |doi=10.1007/978-1-4684-2001-2_9 |isbn=978-1-4684-2003-6 }}</ref>

==== Travelling salesman ====

The decision version of the [[Travelling salesman problem|travelling salesman problem]] is in NP. Given an input matrix of distances between ''n'' cities, the problem is to determine if there is a route visiting all cities with total distance less than ''k''.

A proof can simply be a list of the cities. Then verification can clearly be done in polynomial time. It simply adds the matrix entries corresponding to the paths between the cities.

A [[Nondeterministic Turing machine|nondeterministic Turing machine]] can find such a route as follows:

* At each city it visits it will "guess" the next city to visit, until it has visited every vertex. If it gets stuck, it stops immediately.
* At the end it verifies that the route it has taken has cost less than ''k'' in ''O''(''n'') time.

One can think of each guess as "[[Fork (system call)|forking]]" a new copy of the Turing machine to follow each of the possible paths forward, and if at least one machine finds a route of distance less than ''k'', that machine accepts the input. (Equivalently, this can be thought of as a single Turing machine that always guesses correctly)

A binary search on the range of possible distances can convert the decision version of Traveling Salesman to the optimization version, by calling the decision version repeatedly (a polynomial number of times).<ref>{{Cite web|last=Aaronson|first=Scott|title=P=? NP|url=https://www.scottaaronson.com/papers/pnp.pdf|access-date=13 Apr 2021}}</ref><ref name=":0">{{Cite web|last=Wigderson|first=Avi|title=P, NP and mathematics – a computational complexity perspective|url=https://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/W06/w06.pdf|access-date=13 Apr 2021}}</ref>

==== Subgraph isomorphism ====

The [[Subgraph isomorphism problem|subgraph isomorphism problem]] of determining whether graph {{mvar|G}} contains a subgraph that is isomorphic to graph {{mvar|H}}.<ref>{{Cite book|last1=Garey|first1=Michael R.|title=Computers and Intractability: A Guide to the Theory of NP-Completeness|last2=Johnson|first2=David S.|publisher=W.H. Freeman|year=1979|isbn=0-7167-1045-5}}</ref>

==See also==

* {{annotated link|Turing machine}}

== Notes ==
{{Reflist|group=Note}}

== References ==
{{Reflist}}

== Further reading ==
* [[Biography:Thomas H. Cormen|Thomas H. Cormen]], [[Biography:Charles E. Leiserson|Charles E. Leiserson]], Ronald L. Rivest, and [[Biography:Clifford Stein|Clifford Stein]]. ''[[Introduction to Algorithms]]'', Second Edition. MIT Press and McGraw-Hill, 2001. {{isbn|0-262-03293-7}}. Section 34.2: Polynomial-time verification, pp.&nbsp;979&ndash;983.
* {{cite book | author = Michael Sipser |  year = 1997 | title = Introduction to the Theory of Computation | publisher = PWS Publishing | isbn = 0-534-94728-X | url-access = registration | url = https://archive.org/details/introductiontoth00sips }} Sections 7.3&ndash;7.5 (The Class NP, NP-completeness, Additional NP-complete Problems), pp.&nbsp;241&ndash;271.
* [[Biography:David Harel|David Harel]], Yishai Feldman. Algorithmics: The Spirit of Computing,  Addison-Wesley, Reading, MA, 3rd edition, 2004.

==External links==
* {{CZoo|NP|N#np}}
<!-- * [http://page.mi.fu-berlin.de/aneumann/npc.html Graph of NP-complete Problems]{{dead link|date=March 2010}} -->
* American Scientist primer on traditional and recent complexity theory research: [https://web.archive.org/web/20081012155440/http://www.americanscientist.org/issues/pub/accidental-algorithms "Accidental Algorithms"]

{{ComplexityClasses}}
{{Mathematical logic}}

{{DEFAULTSORT:Np (Complexity)}}
[[Category:Complexity classes]]

{{Sourceattribution|NP (complexity)}}