(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 E. Black.
Entry modified 17 December 2007.
HTML page formatted Mon Dec 17 10:40:08 2007.
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.,
U.S. National Institute of
Standards and Technology. 17 December 2007. (accessed TODAY)
Available from: http://www.nist.gov/dads/HTML/nphard.html