NIST

NP-hard

(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

More information

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 9 September 2013.
HTML page formatted Mon Feb 2 13:10:40 2015.

Cite this as:
Algorithms and Theory of Computation Handbook, CRC Press LLC, 1999, "NP-hard", 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/nphard.html