A common misconception is that the *NP* in "NP-hard" stands for "non-polynomial" when in fact it stands for "**N**on-deterministic **P**olynomial acceptable problems".^{[4]} Although it is suspected that there are no polynomial-time algorithms for NP-hard 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]}

A decision problem *H* is NP-hard when for every problem *L* in NP, there is a polynomial-time 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 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, for instance it also includes search problems, or optimization problems.

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

Note that 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, which is this: 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 traveling salesman problem.^{[8]}

There are decision problems that are NP-hard but not NP-complete, 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 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, while 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 non-deterministic polynomial time (unless NP = PSPACE).^{[9]}

This page was last edited on 24 April 2018, at 19:27 (UTC).

Reference: https://en.wikipedia.org/wiki/NP-hard under CC BY-SA license.

Reference: https://en.wikipedia.org/wiki/NP-hard under CC BY-SA license.

- Non-deterministic Polynomial-time
- Computational Complexity Theory
- NP
- NP
- Reduced
- Polynomial Time
- [1]
- [2]
- [3]
- [4]
- [5]
- P
- NP
- [6]
- Decision Problem
- Polynomial-time Reduction
- [1]
- Polynomial Time
- Oracle Machine
- [7]
- NP-complete
- [1]
- Search Problems
- Optimization Problems
- Approximated
- APX
- PTAS
- FPTAS
- Subset Sum Problem
- Decision Problem
- Traveling Salesman Problem
- [8]
- Halting Problem
- Boolean Satisfiability Problem
- Turing Machine
- Truth Value
- Undecidable
- True Quantified Boolean Formulas
- Polynomial Space
- PSPACE
- [9]

- NP-hard
- Elkanah Watson
- Port Kent (Amtrak Station)
- Sussex Constabulary
- Elkanah Watson House
- Traffic Signals
- South Vietnam
- Malnad College Of Engineering
- John Kavanagh (actor)
- Easyriders
- Isaac Barrow (bishop)
- Church Asylum
- Cognac, France
- Canadian Federal Election, 1891
- County Route 17 (Essex County, New York)
- Warren Clarke
- Medieval Architecture
- Guard Dog
- County Route 71 (Essex County, New York)
- Electional Astrology
- Sri Jayachamarajendra College Of Engineering
- Lantfrid
- Instrumentation Technology
- Twin Lakes, Connecticut
- VH1
- Ausable Chasm, New York
- Illinois Senate
- Port Kent And Hopkinton Turnpike
- Robots.txt
- Theodore Roosevelt International Highway