NP (complexity)

thumb|300px|right|[[Euler diagram for P, NP, NP-complete, and NP-hard set of problems. Under the assumption that P ≠ NP, the existence of problems within NP but outside both P and NP-complete was established by Ladner.]]

In computational complexity theory, NP (nondeterministic polynomial time) is a complexity class used to classify decision problems. NP is the set of decision problems for which the problem instances, where the answer is "yes", have 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.

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, 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.

The complexity class 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 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.

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 is another outstanding question in complexity theory.

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 in <math>O(n^k)</math> time.

Equivalently, NP can be defined using deterministic Turing machines as verifiers. A 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 .
For all x in L, there exists a string y of length q(|x|) such that .
For all x not in L and all strings y of length q(|x|), .

Background

Many computer science problems are contained in NP, like decision versions of many search and optimization problems.

Verifier-based definition

In order to explain the verifier-based definition of NP, consider the subset sum problem:

Assume that we are given some integers, {−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

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 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, 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".), we get the class MA solvable using an Arthur–Merlin protocol with no communication from Arthur to Merlin.

The relationship between BPP and NP is unknown: it is not known whether BPP is a 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 ⊆ BPP.

NP is a class of decision problems; the analogous class of function problems is FNP.

The only known strict inclusions come from the time hierarchy theorem and the 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, NP corresponds precisely to the set of languages definable by existential second-order logic (Fagin's theorem).

NP can be seen as a very simple type of 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 proofs 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 algorithms to be proven.

Examples

P

All problems in 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?

Travelling salesman

The decision version of the 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 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 "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).

Subgraph isomorphism

The subgraph isomorphism problem of determining whether graph contains a subgraph that is isomorphic to graph .

Notes

References

External links

American Scientist primer on traditional and recent complexity theory research: "Accidental Algorithms"