NPcomplete

In complexity theory, the NPcomplete problems are the most difficult problems in NP, in the sense that they are the ones most likely not to be in P. The reason is that if you could find a way to solve an NPcomplete problem quickly, then you could use that algorithm to solve all NP problems quickly. The complexity class consisting of all NPcomplete problems is sometimes referred to as NPC. (A more formal definition is given below. See also Complexity classes P and NP).
One example of an NPcomplete problem is the subset sum problem which is: given a finite set of integers, determine whether any nonempty subset of them sums to zero. A supposed answer is very easy to verify for correctness, but no one knows a significantly faster way to solve the problem than to try every single possible subset, which is very slow.
Contents 
Formal definition of NPcompleteness
A decision problem C is NPcomplete if
 it is in NP and
 every other problem in NP is reducible to it.
"Reducible" here means that for every problem L, there is a polynomialtime manyone reduction, a deterministic algorithm which transforms instances l ∈ L into instances c ∈ C, such that the answer to c is YES if and only if the answer to l is YES. To prove that a NP problem A is in fact a NPcomplete problem we must show that an already known NPcomplete problem reduces to A.
A consequence of this definition is that if we had a polynomial time algorithm for C, we could solve all problems in NP in polynomial time.
This definition was given by Stephen Cook in 1971 (although the term "NPcomplete" did not appear in his paper). At first it seems rather surprising that NPcomplete problems should even exist, but in a celebrated theorem Cook proved that the Boolean satisfiability problem is NPcomplete. In 1972 Richard Karp proved that several other problems were also NPcomplete (see Karp's 21 NPcomplete problems); thus there is a class of NPcomplete problems (besides the Boolean satisfiability problem). Since Cook's original results, thousands of other problems have been shown to be NPcomplete by reductions from other problems previously shown to be NPcomplete; many of these problems are collected in Garey and Johnson's 1979 book Computers and Intractability: A Guide to NPCompleteness.
A problem satisfying condition 2 but not necessarily condition 1 is said to be NPhard. Informally, an NPhard problem is "at least as hard as" any NPcomplete problem, and perhaps harder. For example, choosing the perfect move in certain board games on an arbitrarily large board is NPhard or even strictly harder than the NPcomplete problems.
Example problems
An interesting example is the graph isomorphism problem, the graph theory problem of determining whether a graph isomorphism exists between two graphs. Two graphs are isomorphic if one can be transformed into the other simply by renaming vertices. Consider these two problems:
Graph Isomorphism: Is graph G_{1} isomorphic to graph G_{2}? Subgraph Isomorphism: Is graph G_{1} isomorphic to a subgraph of graph G_{2}?
The Subgraph Isomorphism problem is NPcomplete. The Graph Isomorphism problem is suspected to be neither in P nor NPcomplete, 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 NPcomplete.
The easiest way to prove that some new problem is NPcomplete is first to prove that it is in NP, and then to reduce some known NPcomplete problem to it. Therefore, it is useful to know a variety of NPcomplete problems. Below are a few of them. For more examples of NPcomplete problems, see List of NPcomplete problems.
 Boolean satisfiability problem (SAT)
 Fifteen puzzle
 Knapsack problem
 Hamiltonian cycle problem
 Traveling salesman problem
 Subgraph isomorphism problem
 Subset sum problem
 Clique problem
 Vertex cover problem
 Independent Set problem
 Graph coloring problem
Here is a diagram of some of the NPComplete problems and the reductions typically used to prove their NPcompleteness. In this diagram, an arrow from one problem to another indicates the direction of the reduction. Note that this diagram is misleading as a description of the mathematical relationship between these problems, as there exists a polynomialtime reduction between any two NPcomplete problems; but it indicates where demonstrating this polynomialtime reduction has been easiest.
There is often only a small difference between a problem in P and an NPcomplete problem. For example, the 3SAT problem, a restriction of the boolean satisfiability problem, remains NPcomplete, whereas the slightly more restricted 2SAT problem is in P, and the slightly more general MAX 2SAT problem is again NPcomplete. Determining whether a graph can be colored with 2 colors is in P, but with 3 colors is NPcomplete, even when restricted to planar graphs. Determining if a graph is a cycle or is bipartite is very easy (in L), but finding a maximum bipartite or a maximum cycle subgraph is NPcomplete. A solution of the knapsack problem within any fixed percentage of the optimal solution can be computed in polynomial time, but finding the optimal solution is NPcomplete.
Imperfect solutions
At present, all known algorithms for NPcomplete problems require time that is superpolynomial in the input size. It is unknown whether there are any faster algorithms. Therefore, to solve an NPcomplete problem for any nontrivial problem size, generally one of the following approaches is used:
 Approximation: An algorithm that quickly finds a suboptimal solution that is within a certain (known) range of the optimal one.
 Probabilistic: An algorithm that provably yields good average runtime behavior for a given distribution of the problem instances—ideally, one that assigns low probability to "hard" inputs.
 Special cases: An algorithm that is provably fast if the problem instances belong to a certain special case. Fixedparameter algorithms can be seen as an implementation of this approach.
 Heuristic: An algorithm that works "reasonably well" on many cases, but for which there is no proof that it is both always fast and always produces a good result (a rule of thumb, intuition).
One example of a heuristic algorithm is a suboptimal O(n log n) greedy algorithm used for graph coloring during the register allocation phase of some compilers, a technique called graphcoloring global register allocation. Each vertex is a variable, edges are drawn between variables which are being used at the same time, and colors indicate the register assigned to each variable. Because most RISC machines have a fairly large number of generalpurpose registers, even a heuristic approach is effective for this application.
Alternative approaches
In the definition of NPcomplete given above, the term "reduction" was used in the technical meaning of polynomialtime manyone reduction.
Another type of reduction is polynomialtime Turing reduction. A problem X is polynomialtime Turingreducible to a problem Y if, given a subroutine that solves Y in polynomial time, you could write a program that calls this subroutine and solves X in polynomial time. This contrasts with manyone 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 NPcomplete with Turing reductions instead of manyone reductions, the resulting set of problems won't be smaller than NPcomplete; it is an open question whether it will be any larger. If the two concepts were the same, then it would follow that NP = CoNP. This holds because by their definition the classes of NPcomplete and coNPcomplete problems under Turing reductions are the same and because these classes are both supersets of the same classes defined with manyone reductions. So if both definitions of NPcompleteness are equal then there is a coNPcomplete problem (under both definitions) such as for example the complement of the boolean satisfiability problem that is also NPcomplete (under both definitions). This implies that NP = coNP as is shown in the proof in the article on coNP. Although the question of NP = coNP is an open question it is considered unlikely and therefore it is also unlikely that the two definitions of NPcompleteness are equivalent.
Another type of reduction that is also often used to define NPcompleteness is the logarithmicspace manyone reduction which is a manyone reduction that can be computed with only a logarithmic amount of space. Since every computation that can be done in logarithmic space can also be done in polynomial time it follows that if there is a logarithmicspace manyone reduction then there is also a polynomialtime manyone reduction. This type of reduction is more refined than the more usual polynomialtime manyone reductions and it allows us to distinguish more classes such as Pcomplete. Whether under these types of reductions the definition of NPcomplete changes is still an open problem.
See also
References
 Garey, M. and D. Johnson, Computers and Intractability; A Guide to the Theory of NPCompleteness, 1979. ISBN 0716710455 (This book is a classic, developing the theory, then cataloging many NPComplete problems)
 S. A. Cook, The complexity of theorem proving procedures, Proceedings, Third Annual ACM Symposium on the Theory of Computing, ACM, New York, 1971, 151158
 Paul E. Dunne. An Annotated List of Selected NPcomplete Problems (http://www.csc.liv.ac.uk/~ped/teachadmin/COMP202/annotated_np.html). The University of Liverpool, Dept of Computer Science, COMP202.
 Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski, and Gerhard Woeginger. A compendium of NP optimization problems (http://www.nada.kth.se/~viggo/problemlist/compendium.html). KTH NADA. Stockholm.
 Computational Complexity of Games and Puzzles (http://www.ics.uci.edu/~eppstein/cgt/hard.html)
 Tetris is Hard, Even to Approximate (http://arxiv.org/abs/cs.CC/0210020)
 Minesweeper is NPcomplete! (http://for.mat.bham.ac.uk/R.W.Kaye/minesw/ordmsw.htm)
Important complexity classes (more) 
P  NP  CoNP  NPC  CoNPC  NPhard  UP  #P  #PC  L  NC  PC 
PSPACE  PSPACEC  EXPTIME  EXPSPACE  BQP  BPP  RP  ZPP  PCP  IP  PH 
de:NPVollständigkeit es:NPcompleto he:NPשלמה ja:NP完全 pl:Problem NP zupełny