Wikipedia: NP-complete problem

Difference (from prior major revision) (author diff)

Changed: 1,22c1

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 graph theory 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.

/Talk