NP-hard

complexity A set or property of computational searchproblems. A problem is NP-hard if solving it in polynomialtime 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)