(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
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