NPhard

In computational complexity theory, NPhard (Nondeterministic Polynomialtime hard) refers to the class of decision problems that contains all problems H such that for every decision problem L in NP there exists a polynomialtime manyone reduction to H, written L ≤ H. Informally this class can be described as containing the decision problems that are at least as hard as any problem in NP. This intuition is supported by the fact that if we can find an algorithm A that solves one of these problems H in polynomial time then we can construct a polynomial time algorithm for any problem L in NP by first performing the reduction from L to H and then running the algorithm A.
So, formally, a language L is NPhard if ∀L' in NP, L' ≤ L. If it is also the case that L is in NP, then L is called NPcomplete.
The notion of NPhardness plays an important role in the discussion about the relationship between the complexity classes P and NP. The class NPhard can be understood as the class of problems that are NPcomplete or harder.
A common mistake is to think that the "NP" in "NPhard" stands for "nonpolynomial". Although it is widely suspected that there are no polynomialtime algorithms for these problems, this has never been proven.
Examples
An example of an NPhard problem is the decision problem SUBSETSUM which is this: given a set of integers, does any non empty subset of them add up to zero? That is a yes/no question, and happens to be NPcomplete.
There are also decision problems that are NPhard but not NPcomplete, for example the halting problem. This is the problem "given a program and its input, will it run forever?" That's a yes/no question, so this is a decision problem. It is easy to prove that the halting problem is NPhard but not NPcomplete. For example the boolean satisfiability problem can be reduced to the halting problem by transforming it to the description of a Turing machine that tries all truth value assignments and when it finds one that satisfies the formula it halts and otherwise it goes into an infinite loop. It is also easy to see that the halting problem is not in NP since all problems in NP are decidable and the halting problem is not.
Alternative definitions
An alternative definition of NPhard that is often used replaces polynomialtime manyone reductions with polynomialtime Turing reductions. This notion of NPhardness can be formulated for function problems and not just decision problems.
In this sense, the problem H is NPhard if and only if every decision problem L in NP can be solved in polynomial time by an oracle machine with an oracle for H. (Informally we can think of such a machine as an algorithm that can call a subroutine for solving H and solves L in polynomial time if the subroutine call takes only one step to compute.) If we find a polynomialtime algorithm for an NPhard problem then we have a polynomialtime algorithm for all problems in NPeasy and indeed for all problems in NP.
Whether this definition of NPhardness is equivalent to the one at the beginning of this article (for the case of decision problems) is still an open problem and is discussed in more detail in the article on NPcompleteness.
de:NPSchwere es:NPhard ja:NP困難
Important complexity classes (more) 
P  NP  CoNP  NPC  CoNPC  NPhard  UP  #P  #PC  L  NC  PC 
PSPACE  PSPACEC  EXPTIME  EXPSPACE  BQP  BPP  RP  ZPP  PCP  IP  PH 