# 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 ***N**ondeterministic Turing machine accepts in **P**olynomial 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