NP-hard
<complexity> A set or property of computational {search
problems}. 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}.
[Examples?]
(1995-04-10)