Page "NP-hard" Paragraph 1

NP-hard ( non-deterministic polynomial-time hard ), in computational complexity theory, is a class of problems that are, 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., L ≤ < sub > T </ sub > H ).

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 a 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, or optimization problems.