# NP-hardness

In computational complexity theory, **NP-hardness** (non-deterministic polynomial-time hardness) is the defining property of a class of problems that are informally "at least as hard as the hardest problems in NP". A simple example of an NP-hard problem is the subset sum problem.

A more precise specification is: 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, *H*'s solution can be used to solve *L* in polynomial time.^{[1]}^{[2]} As a consequence, finding a polynomial time algorithm to solve any NP-hard problem would give polynomial time algorithms for all the problems in NP. As it is suspected that , it is unlikely that such an algorithm exists.^{[3]}

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".^{[4]} It is suspected that there are no polynomial-time algorithms for NP-hard problems, but that 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]}

A decision problem *H* is NP-hard when for every problem *L* in NP, there is a polynomial-time many-one 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, an algorithm can be thought of that calls 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 be a polynomial-time reduction from an NP-complete 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 NP-hard to decision problems, and it also includes search problems or optimization problems.

If P ≠ NP, then NP-hard problems could not be solved in polynomial time.

Some NP-hard optimization problems can be polynomial-time approximated up to some constant approximation ratio (in particular, those in APX) or even up to any approximation ratio (those in PTAS or FPTAS).

An example of an NP-hard problem is the decision subset sum problem: given a set of integers, does any non-empty subset of them add up to zero? That is a decision problem and happens to be NP-complete. Another example of an NP-hard problem is the optimization problem of finding the least-cost cyclic route through all nodes of a weighted graph. This is commonly known as the travelling salesman problem.^{[8]}

There are decision problems that are *NP-hard* but not *NP-complete* such as the halting problem. That is the problem which asks "given a program and its input, will it run forever?" That is a *yes*/*no* question and so is a decision problem. It is easy to prove that the halting problem is NP-hard but not NP-complete. 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, but the halting problem, in general, is undecidable. There are also NP-hard problems that are neither *NP-complete* nor *Undecidable*. For instance, the language of true quantified Boolean formulas is decidable in polynomial space, but not in non-deterministic polynomial time (unless NP = PSPACE).^{[9]}

NP-hard 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-hard problems are often tackled with rules-based languages in areas including: