Wikipedia: NP-complete problem

Difference (from prior author revision) (major diff, minor diff)

Changed: 1,34c1

The complexity class NP-complete is a set of problems that are in some sense the hardest problems in NP. If you can find a way to solve an NP-complete problem quickly, then you can use that algorithm to solve all NP problems quickly. (see Complexity classes P and NP).

One example of an NP-complete problem is [Subset Sum]? which is: given a set of integers, determine whether any subset of them adds up to zero. It's easy to check a supposed answer to see if it's right, but no one knows a fast way to solve the problem.

A more formal definition: NP-complete is a subset of NP. A problem is in NP-complete if and only if every problem in NP is reducible to it.

In this context, "reducible" means "polytime, many-to-one reducible". A problem X is polytime, many-to-one reducible to a problem Y if there exists a polytime algorithm that can take any instance of X as input, and will return as output an instance of Y, such that both instances have the same truth value.

Another type of reducibility is polytime, Turing Reducibility. A problem X is polytime, Turing reducible to a problem Y if, given a subroutine that solves Y in polytime, you could write a program that solves X in polytime. This contrasts with many-to-one reducibility, which has the restriction that the program can only call the subroutine once, and the return value of the subroutine must be the return value of the program.

The set NP-complete is usually defined using many-to-one reductions. If it had been defined with Turing reductions instead, the set couldn't be any smaller. It isn't known whether that change would make it any larger. ("Isn't known" means not known to me, or to the theory books I've consulted, though none of the theory books claimed it to be an open problem).

It isn't really correct to say that NP-complete problems are the hardest problems in NP. Assuming that P and NP are not equal, there are guaranteed to be an infinite number of problems that are in NP, but are neither NP-complete nor in P. Some of these problems may actually have higher complexity than some of the NP-complete problems.

An interesting example is the problem of graph isomorphism. Two graphs are isomorphic if one can be transformed into the other simply by renaming nodes. Consider these two problems:

Graph Isomorphism: Is graph G₁ isomorphic to graph G₂?
Subgraph Isomorphism: Is graph G₁ isomorphic to a subgraph of graph G₂?

The Subgraph Isomorphism problem is NP-complete. The Graph Isomorphism problem is suspected to be neither P nor NP-complete, though it is obviously NP. This is an example of a problem that is thought to be hard, but isn't thought to be NP-complete.

All of the above discussion has talked as if P meant "easy" and "not in P" meant "hard". That is not always true in practice, for several reasons:

First, they ignore constant factors. A problem that takes time 10¹⁰⁰⁰n is P (in fact, it's linear time), but is completely intractable in practice. A problem that takes time 10^-100002ⁿ is not P (in fact, it's exponential time), but is very tractable for values of n up into the thousands.

Second, they ignore the size of the exponents. A problem with time n¹⁰⁰⁰ is P, yet intractable. A problem with time 2^n/1000 is not P, yet is tractable for n up into the thousands.

Third, they only look at worst case times. There might be a problem that arises in the real world. Most of the time, it can be solved in time n, but on very rare occasions you'll see an instance of the problem that takes time 2ⁿ. This problem might have an average time that is polynomial, but the worst case is exponential, so the problem wouldn't be in P.

Fourth, they only look at deterministic solutions. There might be a problem that you can solve by repeatedly making up random guesses and checking them until you find the answer. It might be that every instance can be solved with only n guesses on average, but requires 2ⁿ guesses in the worst case.

/Talk