NP (complexity)

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 that can be "verified" by a deterministic Turing machine in polynomial time; we will explain this in more detail below.

Contents

1 Introduction and applications 2 Why some NP problems are hard to solve 3 Other characterizations 4 Example 5 References

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 a simple example, consider the problem of determining whether a number n is a composite number. For large numbers, this seems like a very difficult problem to solve efficiently; the simplest approaches require time which is exponential in log n, the number of input bits. On the other hand, once we've found a candidate factor of n, the following function can quickly tell us whether it really is a factor:

 boolean isNontrivialFactor(n, d)
     if n is divisible by d and
        d ≠ 1 and d ≠ n
         return true
     else
         return false

If n is composite, then this function will return true for some input d. If n is prime, however, this function will always return false, regardless of d. All problems in NP have a deterministic function just like this, which accepts only when given both an input and proof that the input is in the language. We must be able to check if the proof is correct in polynomial time. We call such a machine a verifier for the problem.

If we have a nondeterministic machine, testing a number for compositeness is easy. It can branch into n different paths in just O(log n) steps; then, each of these can call isNontrivialFactor(n, d) for one d. If any succeed, the number is composite; otherwise, it is prime.

Thus, the challenge of NP problems is to efficiently find the answer, given an efficient (polynomial-time) way of verifying it once it is found. This challenge was solved for compositeness testing only in 2002; there is still no known polynomial-time way to solve the more general factoring problem of determining whether a number between 1 and m divides n.

But these are only some of the easiest problems in NP. Additional examples include:

• 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 is satisfiable 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 algorithms that decide the problems in NP in time which is polynomial in the input size, which is generally considered efficient. However, there are a large number of problems in NP that defy such attempts, seeming to require superpolynomial time. Whether these problems really aren't solvable in polynomial time is one of the greatest open questions in computer science (see Complexity classes P and NP 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.

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

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 computation problem (finding the route and its exact length) quickly as well.

References

• Complexity Zoo: NP (http://www.complexityzoo.com/#np)

Important complexity classes (more)

P | NP | Co-NP | NP-C | Co-NP-C | NP-hard | UP | #P | #P-C | L | NC | P-C

PSPACE | PSPACE-C | EXPTIME | EXPSPACE | BQP | BPP | RP | ZPP | PCP | IP | PH

cs:Nedeterministicky polynomiální problém de:NP (Komplexitätsklasse) es:NP ja:NP pl:Problem NP he:NP