TOPICS
Search

NP-Hard Problem


A problem is NP-hard if an algorithm for solving it can be translated into one for solving any 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, Hamiltonian Cycle, Maxcut, NP-Complete Problem, NP-Problem, P-Problem, P Versus NP Problem, Satisfiability Problem, Vertex Cover

Explore with Wolfram|Alpha

Cite this as:

Weisstein, Eric W. "NP-Hard Problem." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/NP-HardProblem.html

Subject classifications