Definition of Np-hard

FOLDOC
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)

Search Dictionary:
Search Web Search Dictionary



NP-hard definition was found in categories: Language, Idioms & Slang(1)  Encyclopedia(1)  

NP-hard Definition from Language, Idioms & Slang Dictionaries & Glossaries

hEnglish - advanced version
np-hard
np-hard
a set or property of computational search problem s. 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.


NP-hard Definition from Encyclopedia Dictionaries & Glossaries

Wikipedia English - The Free Encyclopedia
NP-hard
For a gentler introduction, see P = NP problem.
NP-hard (nondeterministic polynomial-time hard), in computational complexity theory, is a class of problems informally "at least as hard as the hardest problems in NP." A problem H is NP-hard if and only if there is an NP-complete problem L that is polynomial time Turing-reducible to H, i.e. . In other words, L can be solved in polynomial time by an oracle machine with an oracle for H. Informally we can think of an algorithm that can call such an oracle machine as subroutine for solving H, and solves L in polynomial time if the subroutine call takes only one step to compute. NP-hard problems may be of any type: decision problems, search problems, optimization problems.

See more at Wikipedia.org...