(definition)

**Definition:**
The *complexity class* of *decision problems* that are intrinsically harder than those that can be solved by a *nondeterministic Turing machine* in *polynomial time*. When a decision version of a combinatorial *optimization problem* is proved to belong to the class of *NP-complete* problems, then the optimization version is NP-hard.

**Specialization** (... is a kind of me.)

*unbounded knapsack problem*.

**See also**
*strongly NP-hard*.

*Note:
For example, "is there a Hamiltonian cycle with length less than k" is NP-complete: it is easy to determine if a proposed certificate has length less than k. The optimization problem, "what is the shortest tour?", is NP-hard, since there is no easy way to determine if a certificate is the shortest. *

Another NP-complete problem is to decide if there exist k *star-shaped polygons* whose union is equal to a given simple polygon, for some parameter k. The optimization problem, i.e., finding the minimum number (least k) of star-shaped polygons whose union is equal to a given simple polygon, is NP-hard.

* From Algorithms and Theory of Computation Handbook, page 19-26, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.*

Author: CRC-A

History, definitions, examples, etc. given in Comp.Theory FAQ, scroll down to **P vs. NP**.

Scott Aaronson's Complexity Zoo

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 5 January 2021.

HTML page formatted Tue Jan 5 09:25:05 2021.

Cite this as:

Algorithms and Theory of Computation Handbook, CRC Press LLC, 1999, "NP-hard", in
*Dictionary of Algorithms and Data Structures* [online], Paul E. Black, ed. 5 January 2021. (accessed TODAY)
Available from: https://www.nist.gov/dads/HTML/nphard.html