NP-hard (nondeterministic polynomial-time hard), in computational complexity theory, is a class of problems 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 <= T_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 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, optimization problems.
As consequences of such definition, we have (note that these are claims, not definitions):
problem H is at least as hard as L, because H can be used to solve L;
since L is NP-complete, and hence the hardest in class NP, also problem H is at least as hard as NP, but H does not have to be in NP and hence does not have to be a decision problem;
since NP-complete problems transform to each other by polynomial-time many-one reduction (also called polynomial transformation), therefore all NP-complete problems can be solved in polynomial time by a reduction to H, thus all problems in NP reduce to H; note however, that this involves combining two different transformations: from NP-complete decision problems to NP-complete problem L by polynomial transformation, and from L to H by polynomial Turing reduction;
if there is a polynomial algorithm for any NP-hard problem, then there are polynomial algorithms for all problems in NP, and hence P = NP;
if P != NP, then NP-hard problems have no solutions in polynomial time, while P = NP does not resolve whether the NP-hard problems can be solved in polynomial time;
if an optimization problem H has an NP-complete decision version L, then H is NP-hard;
if H is in NP, then H is also NP-complete because in this case the existing polynomial Turing transformation fulfills the requirements of polynomial time transformation.
A common mistake is to think that the "NP" in "NP-hard" stands for "non-polynomial". Although it is widely suspected that there are no polynomial-time algorithms for these problems, this has never been proven.
Reference:
http://en.wikipedia.org/wiki/Np_hard
