NPhard (nondeterministic polynomialtime 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 NPhard if and only if there is an NPcomplete problem L that is polynomial time Turingreducible 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 a subroutine for solving H, and solves L in polynomial time, if the subroutine call takes only one step to compute. NPhard problems may be of any type: decision problems, search problems, or optimization problems.
As consequences of 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 NPcomplete, 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 (even if it is a decision problem, it need not be in NP);
 Since NPcomplete problems transform to each other by polynomialtime manyone reduction (also called polynomial transformation), all NPcomplete 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 NPcomplete decision problems to NPcomplete problem L by polynomial transformation, and from L to H by polynomial Turing reduction;
 If there is a polynomial algorithm for any NPhard problem, then there are polynomial algorithms for all problems in NP, and hence P = NP;
 If P ≠ NP, then NPhard problems have no solutions in polynomial time, while P = NP does not resolve whether the NPhard problems can be solved in polynomial time;
 If an optimization problem H has an NPcomplete decision version L, then H is NPhard.
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 NPhard problems, this has never been proven. Moreover, the class NP also contains all problems which can be solved in polynomial time.
Contents
Examples
An example of an NPhard problem is the decision subset sum problem, which is this: given a set of integers, does any nonempty subset of them add up to zero? That is a decision problem, and happens to be NPcomplete. Another example of an NPhard problem is the optimization problem of finding the leastcost cyclic route through all nodes of a weighted graph. This is commonly known as the Traveling Salesman Problem.
There are decision problems that are NPhard but not NPcomplete, for example the halting problem. This is the problem which asks "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 in a finite number of operations, while the halting problem, in general, is not. There are also NPhard problems that are neither NPcomplete nor undecidable. For instance, the language of True quantified Boolean formulas is decidable in polynomial space, but not nondeterministic polynomial time (unless NP = PSPACE).
Full article ▸
