NIST

NP-complete

(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.

See also NP-hard, P.

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

Implementation

Stas Busygin's home page with QUALEX and SAT01 (C++).

More information

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.


Go to the Dictionary of Algorithms and Data Structures home page.

If you have suggestions, corrections, or comments, please get in touch with Paul Black.

Entry modified 9 September 2013.
HTML page formatted Tue May 6 13:48:56 2014.

Cite this as:
Paul E. Black, "NP-complete", in Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 9 September 2013. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/npcomplete.html