NP complexity: Encyclopedia II - NP complexity - Introduction and applications

NP complexity - 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 (see Big O notation); 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 (see AKS Primality Test) 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.

Adapted from the Wikipedia article "Introduction and applications", under the G.N U Free Docmentation License. Please also see http://en.wikipedia.org/wiki