One example of an NP-complete problem is [Subset Sum]? which is: given a finite 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: A decision problem C is NP-complete if it is in NP and if every other problem in NP is reducible to it, in the sense that for every other NP problem L we can find a polytime algorithm which transforms instances of L into instances of C such that the two instances have the same truth values. As a consequence, if we had a polytime algorithm for C, we could solve all NP problems in polytime.
This definition was given by Cook in 1971. At first it seems rather surprising that NP-complete problems should even exist, but in a celebrated theorem Cook proved that the Boolean satisfiability problem is NP-complete.
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:
![[Home]](wikipedia.png)
Graph Isomorphism: Is graph G1 isomorphic to graph G2?
Subgraph Isomorphism: Is graph G1 isomorphic to a subgraph of graph G2?
The Subgraph Isomorphism problem is NP-complete. The Graph Isomorphism problem is suspected to be neither in P nor NP-complete, though it is obviously in NP. This is an example of a problem that is thought to be hard, but isn't thought to be NP-complete.
The easiest way to prove that some new problem is NP-complete is to reduce some known NP-complete problem to it. Therefore, it is useful to know a number of NP-complete problems. Here are some famous ones:
| Boolean satisfiability problem |
| [3-CNF satisfiability problem]? |
| [Circuit satisfiability problem]? |
| [Traveling Salesman problem]? |
| [Subset sum problem]? |
| [Subgraph isomorphism problem]? |
In the definition of NP-complete given above, the term "reduction" was used in the technical meaning of "polytime, many-to-one reduction". 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.
If one defines the analogue to NP-complete with Turing reductions instead of many-to-one reductions, the resulting set won't be smaller than NP-complete; it isn't known whether it will be 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).