<*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?]

Last updated: 1995-04-10

Try this search on Wikipedia, OneLook, Google

**Nearby terms:**
np « NPC « NP-complete « **NP-hard** » NPL » NPPL » N-Prolog

Loading

Copyright Denis Howe 1985