info prev up next book cdrom email home

NP-Hard Problem

A problem is NP-hard if an Algorithm for solving it can be translated into one for solving any other NP-Problem (nondeterministic Polynomial time) problem. NP-hard therefore means ``at least as hard as any NP-Problem,'' although it might, in fact, be harder.

See also Complexity Theory, Hitting Set, NP-Complete Problem, NP-Problem, P-Problem, Satisfiability Problem

© 1996-9 Eric W. Weisstein