# NP-Hard Task

An NP-Hard Task is a computational task that is at least as hard as the hardest NP-complete task.

**AKA:**NP-Hard.**Example(s):**- Exact Bayesian Inference with a Bayesian Network.
- a Shortest-Cycle Search Task, such as a traveling salesperson task.
- a Halting Decision Task/halting problem.
- …

**Counter-Example(s):****See:**Computational Complexity Analysis Task, Packing Task, NP (Complexity), Computational Complexity Theory, Reduction_(Complexity), Polynomial Time.

## References

### 2015

- (Wikipedia, 2015) ⇒ http://en.wikipedia.org/wiki/NP-hardness Retrieved:2015-11-2.
**NP-hardness**(*n*on-deterministic*p*olynomial-time hard), in computational complexity theory, is a class of problems that are, informally, "at least as hard as the hardest problems in NP”. More precisely, a problem*H*is NP-hard when every problem*L*in NP can be reduced in polynomial time to*H*. As a consequence, finding a polynomial algorithm to solve any NP-hard problem would give polynomial algorithms for all the problems in NP, which is unlikely as many of them are considered hard.A common mistake is thinking that the

*NP*in "NP-hard" stands for "non-polynomial". Although it is widely suspected that there are no polynomial-time algorithms for NP-hard problems, this has never been proven. Moreover, the class NP also contains all problems which can be solved in polynomial time.

- (Wikipedia, 2015) ⇒ http://en.wikipedia.org/wiki/NP-hardness#Definition Retrieved:2015-11-2.
- A decision problem
*H*is NP-hard when for any problem*L*in NP, there is a polynomial-time reduction from*L*to*H*An equivalent definition is to require that any problem*L*in NP 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.Another definition is to require that there is a polynomial-time reduction from an NP-complete problem

*G*to*H*. 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. It does not restrict the class NP-hard to decision problems, for instance it also includes search problems, or optimization problems.

- A decision problem

### 2013

- http://en.wikipedia.org/wiki/NP-hard
**NP-hard**(**N**on-deterministic**P**olynomial-time 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 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 a 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, 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 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 (even if it is a decision problem, it need not be in NP); - Since NP-complete problems transform to each other by polynomial-time many-one reduction (also called polynomial transformation), 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 cannot be solved 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.

- Problem
- 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 NP-hard problems, this has never been proven. Moreover, the class NP also contains all problems which can be solved in polynomial time.