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

(01 Mar 1995)

NP, Np, np, NPC, NP-complete < Prev | Next > NPH insulin, NPL, NPN, npo

Bookmark with: icon icon icon icon iconword visualiser Go and visit our forums Community Forums