NP-hardness

For a gentler introduction, see P versus NP problem.
Euler diagram for P, NP, NP-complete, and NP-hard set of problems.
Euler diagram for P, NP, NP-complete, and NP-hard set of problems. The left side is valid under the assumption that P≠NP, while the right side is valid under the assumption that P=NP (except that the empty language and its complement are never NP-complete)

NP-hardness (non-deterministic polynomial-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, 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 NP-hard problem would give polynomial algorithms for all the problems in NP, which is unlikely as many of them are considered hard.[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] Although it is suspected that there are no polynomial-time algorithms for NP-hard problems, this has never been proven.[5] Moreover, the class P in which all problems can be solved in polynomial time, is contained in the NP class.[6]

Definition

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

Consequences

Examples

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]

NP-naming convention

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
Class of computational problems for which a given solution can be verified as a solution in polynomial time by a deterministic Turing machine (or solvable by a non-deterministic Turing machine in polynomial time).
NP-hard
Class of problems which are at least as hard as the hardest problems in NP. Problems that are NP-hard do not have to be elements of NP; indeed, they may not even be decidable.
NP-complete
Class of problems which contains the hardest problems in NP. Each NP-complete problem has to be in NP.
NP-easy
At most as hard as NP, but not necessarily in NP, since they may not be decision problems.
NP-equivalent
Problems that are both NP-hard and NP-easy, but not necessarily in NP, since they may not be decision problems.
NP-intermediate
If P and NP are different, then there exist problems in the region of NP that fall between P and the NP-complete problems. (If P and NP are the same class, then NP-intermediate problems do not exist.)

Application areas

NP-hard problems are often tackled with rules-based languages in areas including:

References

  1. 1 2 3 Leeuwen, Jan van, ed. (1998). Handbook of Theoretical Computer Science. Vol. A, Algorithms and complexity. Amsterdam: Elsevier. ISBN 0262720140. OCLC 247934368.
  2. ↑ Knuth, Donald (1974). "Postscript about NP-hard problems". ACM SIGACT News. 6 (2): 15–16. doi:10.1145/1008304.1008305. Retrieved 30 January 2016.
  3. ↑ Daniel Pierre Bovet; Pierluigi Crescenzi. Introduction to the Theory of Complexity. Prentice Hall. p. 69. ISBN 0-13-915380-2.
  4. ↑ "P and NP". www.cs.uky.edu. Retrieved 2016-09-25.
  5. ↑ "Shtetl-Optimized » Blog Archive » The Scientific Case for P≠NP". www.scottaaronson.com. Retrieved 2016-09-25.
  6. ↑ "PHYS771 Lecture 6: P, NP, and Friends". www.scottaaronson.com. Retrieved 2016-09-25.
  7. ↑ V. J. Rayward-Smith (1986). A First Course in Computability. Blackwell. p. 159. ISBN 0-632-01307-9.
  8. ↑ 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 0-471-90413-9.
  9. ↑ More precisely, this language is PSPACE-complete; see e.g. Wegener, Ingo (2005), Complexity Theory: Exploring the Limits of Efficient Algorithms, Springer, p. 189, ISBN 9783540210450.
This article is issued from Wikipedia - version of the 11/28/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.