NP-hardness

NP-hardness (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". More precisely, a problem H is NP-hard when every problem L in NP can be reduced in polynomial time to H, that is: assuming a solution for H takes 1 unit time, we can use H‎'s solution to solve L in polynomial time. As a consequence, finding a polynomial algorithm to solve any NP-hard problem would give polynomial algorithms for all the problems in NP, which is unlikely as many of them are considered hard.

A common misconception is that the NP in "NP-hard" stands for "non-polynomial" when in fact it stands for "Non-deterministic Polynomial acceptable problems". Although it is suspected that there are no polynomial-time algorithms for NP-hard problems, this has never been proven. Moreover, the class P in which all problems can be solved in polynomial time, is contained in the NP class.

A decision problem H is NP-hard when for every problem L in NP, there is a polynomial-time reduction from L to H An equivalent definition is to require that every problem L in NP 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.

Another definition is to require that there is a polynomial-time reduction from an NP-complete problem G to H. As any problem L in NP reduces in polynomial time to G, L reduces in turn to H in polynomial time so this new definition implies the previous one. Awkwardly, it does not restrict the class NP-hard to decision problems, for instance it also includes search problems, or optimization problems.

...
Wikipedia