(definition)
Definition: The complexity class of decision problems for which answers can be checked for correctness, given a certificate, by an algorithm whose run time is polynomial in the size of the input (that is, it is NP) and no other NP problem is more than a polynomial factor harder. Informally, a problem is NP-complete if answers can be verified quickly, and a quick algorithm to solve this problem can be used to solve all other NP problems quickly.
Generalization (I am a kind of ...)
NP.
Note: A trivial example of NP, but (presumably) not NP-complete is finding the bitwise AND of two strings of N boolean bits. The problem is NP, since one can quickly (in time Θ(N)) verify that the answer is correct, but knowing how to AND two bit strings doesn't help one quickly find, say, a Hamiltonian cycle or tour of a graph. So bitwise AND is not NP-complete (as far as we know).
Other well-known NP-complete problems are satisfiability (SAT), traveling salesman, the bin packing problem, and the knapsack problem. (Strictly the related decision problems are NP-complete.)
"NP" comes from the class that a Nondeterministic Turing machine accepts in Polynomial time.
Author: PEB
History, definitions, examples, etc. given in Comp.Theory FAQ, scroll down to P vs. NP. Eppstein's longer, but very good introduction to NP-completeness, with sections like Why should we care?, Examples of problems in different classes, and how to prove a problem is NP-complete. A compendium of NP optimization problems.
Scott Aaronson's Complexity Zoo
From xkcd by Creative Commons Attribution-NonCommercial 2.5 License.
If you have suggestions, corrections, or comments, please get in touch with Paul Black.
Entry modified 22 April 2015.
HTML page formatted Mon May 18 09:42:24 2015.
Cite this as:
Paul E. Black, "NP-complete", in
Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 22 April 2015. (accessed TODAY)
Available from: http://www.nist.gov/dads/HTML/npcomplete.html