# 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 E. Black.

Entry modified 5 September 2012.

HTML page formatted Wed Sep 5 11:48:01 2012.

Cite this as:

Paul E. Black, "NP-complete", in
*Dictionary of Algorithms and Data
Structures* [online], Paul E. Black, ed.,
U.S. National Institute of
Standards and Technology. 5 September 2012. (accessed TODAY)
Available from: http://www.nist.gov/dads/HTML/npcomplete.html