Np

 

symbol for element neptunium.

In computational complexity theory, NP ("Non-deterministic Polynomial time") is the set of decision problems solvable in polynomial time on a non-deterministic Turing machine. Equivalently, it is the set of problems whose solutions can be "verified" by a deterministic Turing machine in polynomial time.

Formal definition

The complexity class NP can be defined in terms of NTIME as follows:

Introduction and applications

The importance of this class of decision problems is that it contains many interesting searching and optimization problems where we want to know if there exists a certain solution for a certain problem.

As an example, consider the following simple problem. We have a set of numbers such as {−7, −3, −2, 5, 8}, and we wish to know whether some subset of the numbers sums to zero. In this case the answer is yes, since the subset {-3, -2, 5} sums to zero. This is known as the subset sum problem. As the set becomes larger, this problem rapidly becomes more difficult, and no fast, scalable algorithm for it has ever been found.

On the other hand, if as above you are supplied a particular subset, it is quick and easy to verify whether or not it sums to zero. All problems in NP have a deterministic polynomial time algorithm just like this, which accepts only when given both an input and "proof" that the input is in the language. We call such an algorithm a verifier for the problem.

Thus, the challenge of NP problems is to find the answer efficiently, given an efficient way of verifying it once it is found.

Additional examples of problems in NP include:

• The integer factorization problem of finding a number which (nontrivially) divides a given number, as in 6 = 2 × 3;
• The graph isomorphism problem of determining whether two graphs can be drawn identically;
• The traveling salesman problem, where we want to know if there is a route of some length that goes through all the nodes in a certain network;
• The boolean satisfiability problem, where we want to know if a certain formula in propositional logic with boolean variables can be true for some value of the variables or not.

See NP-complete for a list of additional important problems in NP.

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 superpolynomial time. Whether these problems really aren't decidable in polynomial time is one of the greatest open questions in computer science (see P=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.

Equivalency 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 nondeterministic 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 nondeterministic TM called A accepting a given language L. At each of its polynomially-many steps, the machine's computation tree branches in at most a constant 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 its accepts at the end. If A rejects the input, there is no accepting path, and the verifier will never accept.

Relationship to other classes

NP contains all problems in 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 don't have to consider proofs longer than this). NP is also contained in EXPTIME, since the same algorithm operates in exponential time.

The complement of NP, co-NP, contains those problems which have a simple proof for no instances, sometimes called counterexamples. For example, primality testing 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, higher only than P.

NP is defined using only deterministic machines. If we permit the verifier to be probabilistic (specifically, a BPP machine), we get the class MA solvable using a Arthur-Merlin protocol with no communication from Merlin to Arthur.

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

Other characterizations

There is also a simple logical characterization of NP: it contains precisely those languages expressible in second-order logic restricted to exclude universal quantification over relations, functions, and subsets.

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.

Example

The decision version of the traveling 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 nondeterministic Turing machine can find such a route as follows:

• At each city it visits it "guesses" 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)

What makes this a natural decision version of the problem is that, if we could solve this problem quickly, we could use binary search to solve the original optimization version of the problem (finding the route and its exact length) quickly as well.

References

• Complexity Zoo: NP
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and 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.979–983.
• Michael Sipser (1997). Introduction to the Theory of Computation. PWS Publishing. ISBN 0-534-94728-X.  Sections 7.3–7.5 (The Class NP, NP-completeness, Additional NP-complete Problems), pp.241–271.
• David Harel, Yishai Feldman. Algorithmics: The Spirit of Computing, Addison-Wesley, Reading, MA, 3rd edition, 2004.

Important complexity classes (more)
P • NP • co-NP • NP-C • co-NP-C • NP-hard • UP • #P • #P-C • L • NL • NC • P-C • PSPACE • PSPACE-C • EXPTIME • NEXPTIME • EXPSPACE • 2-EXPTIME • PR • RE • Co-RE • RE-C • Co-RE-C • R • BQP • BPP • RP • ZPP • PCP • IP • PH

Donate to Wikimedia