NPhardness
NPhardness (nondeterministic polynomialtime hardness), in computational complexity theory, is the defining property of a class of problems that are, informally, "at least as hard as the hardest problems in NP". More precisely, a problem H is NPhard 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.^{[1]}^{[2]} As a consequence, finding a polynomial algorithm to solve any NPhard problem would give polynomial algorithms for all the problems in NP, which is unlikely as many of them are considered difficult.^{[3]}
A common misconception is that the NP in "NPhard" stands for "nonpolynomial" when in fact it stands for "nondeterministic polynomial acceptable problems".^{[4]} Although it is suspected that there are no polynomialtime algorithms for NPhard problems, this has not been proven.^{[5]} Moreover, the class P in which all problems can be solved in polynomial time, is contained in the NP class.^{[6]}
Contents
Definition
A decision problem H is NPhard when for every problem L in NP, there is a polynomialtime reduction from L to H.^{[1]}^{:80} 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.^{[7]} 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 polynomialtime reduction from an NPcomplete problem G to H.^{[1]}^{:91} 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 NPhard to decision problems, for instance it also includes search problems, or optimization problems.
Consequences
If P ≠ NP, then NPhard problems cannot be solved in polynomial time.
Note that some NPhard optimization problems can be polynomialtime approximated up to some constant approximation ratio (in particular, those in APX) or even up to any approximation ratio (those in PTAS or FPTAS).
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.^{[8]}
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 is 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 undecidable. 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).^{[9]}
NPnaming convention
NPhard problems do not have to be elements of the complexity class NP. As NP plays a central role in computational complexity, it is used as the basis of several classes:
 NP
 Class of computational decision problems for which a given solution can be verified as a solution in polynomial time by a deterministic Turing machine (or solvable by a nondeterministic Turing machine in polynomial time).
 NPhard
 Class of decision problems which are at least as hard as the hardest problems in NP. Problems that are NPhard do not have to be elements of NP; indeed, they may not even be decidable.
 NPcomplete
 Class of decision problems which contains the hardest problems in NP. Each NPcomplete problem has to be in NP.
 NPeasy
 At most as hard as NP, but not necessarily in NP.
 NPequivalent
 Decision problems that are both NPhard and NPeasy, but not necessarily in NP.
 NPintermediate
 If P and NP are different, then there exist decision problems in the region of NP that fall between P and the NPcomplete problems. (If P and NP are the same class, then NPintermediate problems do not exist because in this case every NPcomplete problem would fall in P, and by definition, every problem in NP can be reduced to an NPcomplete problem.)
Application areas
This section needs expansion. You can help by adding to it. (January 2015)

NPhard problems are often tackled with rulesbased languages in areas including:
 Approximate computing
 Configuration
 Cryptography
 Data mining
 Decision support
 Phylogenetics
 Planning
 Process monitoring and control
 Rosters or schedules
 Routing/vehicle routing
 Scheduling
 Selection
 Tutoring systems
References
 ^ ^{a} ^{b} ^{c} Leeuwen, Jan van, ed. (1998). Handbook of Theoretical Computer Science. Vol. A, Algorithms and complexity. Amsterdam: Elsevier. ISBN 0262720140. OCLC 247934368.
 ^ Knuth, Donald (1974). "Postscript about NPhard problems". ACM SIGACT News. 6 (2): 15–16. doi:10.1145/1008304.1008305. Retrieved 30 January 2016.
 ^ Daniel Pierre Bovet; Pierluigi Crescenzi. Introduction to the Theory of Complexity. Prentice Hall. p. 69. ISBN 0139153802.
 ^ "P and NP". www.cs.uky.edu. Retrieved 20160925.
 ^ "ShtetlOptimized » Blog Archive » The Scientific Case for P≠NP". www.scottaaronson.com. Retrieved 20160925.
 ^ "PHYS771 Lecture 6: P, NP, and Friends". www.scottaaronson.com. Retrieved 20160925.
 ^ V. J. RaywardSmith (1986). A First Course in Computability. Blackwell. p. 159. ISBN 0632013079.
 ^ Lawler, E. L.; Lenstra, J. K.; Rinnooy Kan, A. H. G.; Shmoys, D. B. (1985), The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization, John Wiley & Sons, ISBN 0471904139.
 ^ More precisely, this language is PSPACEcomplete; see e.g. Wegener, Ingo (2005), Complexity Theory: Exploring the Limits of Efficient Algorithms, Springer, p. 189, ISBN 9783540210450.
 Michael R. Garey and David S. Johnson (1979). Computers and Intractability: A Guide to the Theory of NPCompleteness. W.H. Freeman. ISBN 0716710455.