<complexity> A set or property of computational search problem
A problem is NP-hard if solving it in polynomial time would make it possible to solve all problems in class NP
in polynomial time.
Some NP-hard problems are also in NP
(these are called "NP-complete
"), some are not.
If you could reduce an NP
problem to an NP-hard problem and then solve it in polynomial time, you could solve all NP problems.
See also computational complexity