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 edited by Pierluigi Crescenzi and Viggo Kann.

Scott Aaronson's Complexity Zoo

Caption: My hobby: embedding NP-complete problems in restaurant orders. Left panel is a menu. In the right panel, person ordering says, 'We'd like exactly $15.05 worth of appetizers, please.' followed by mentions of knapsack and other NP-complete problems.
From xkcd 287 by Randall Munroe. 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 26 April 2021.
HTML page formatted Mon Apr 26 09:29:23 2021.

Cite this as:
Paul E. Black, "NP-complete", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed. 26 April 2021. (accessed TODAY) Available from: https://www.nist.gov/dads/HTML/npcomplete.html