NP-HARD


Meaning of NP-HARD in English

< complexity > 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.

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)

FOLDOC computer English dictionary.      Английский словарь по компьютерам FOLDOC.