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)
Nearby terms:
np « NPC « NP-complete « NP-hard » NPL » NPPL
» N-Prolog
|
