Editing NP-hardness

{{short description|Complexity class}}
{{for|a gentler introduction|P versus NP problem}}
[[File:P np np-complete np-hard.svg|alt=Euler diagram for P, NP, NP-complete, and NP-hard set of problems.|thumb|300px|[[Euler diagram]] for [[P (complexity)|P]], [[NP (complexity)|NP]], NP-complete, and NP-hard set of problems. The left side is valid under the assumption that [[P versus NP problem|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)]]
In [[computational complexity theory]], a computational problem ''H'' is called '''NP-hard''' if, for  every problem ''L'' which can be solved in [[NP (complexity)|non-deterministic polynomial-time]], there is a [[Polynomial time reduction|polynomial-time reduction]] from ''L'' 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.<ref name="Leeuwen">{{cite book |editor1-first=Jan van |editor1-last=Leeuwen |editor1-link=Jan van Leeuwen |year=1998 |title=Handbook of Theoretical Computer Science |volume=A, Algorithms and complexity |location=Amsterdam |publisher=Elsevier |isbn=0262720140 |oclc=247934368}}</ref><ref>{{cite journal|last1=Knuth|first1=Donald|title=Postscript about NP-hard problems|journal=ACM SIGACT News|date=1974|volume=6|issue=2|pages=15–16|doi=10.1145/1008304.1008305|s2cid=46480926}}</ref> As a consequence, finding a polynomial time algorithm to solve a single NP-hard problem would give polynomial time algorithms for all the problems in the complexity class [[NP (complexity)|NP]]. As it is suspected, but unproven, that [[P versus NP|P≠NP]], it is unlikely that any polynomial-time algorithms for NP-hard problems exist.<ref>{{cite book |author1=Daniel Pierre Bovet |title=Introduction to the Theory of Complexity |author2=Pierluigi Crescenzi |publisher=Prentice Hall |year=1994 |isbn=0-13-915380-2 |page=69}}</ref><ref>{{Cite web |title=Shtetl-Optimized » Blog Archive » The Scientific Case for P≠NP |url=http://www.scottaaronson.com/blog/?p=1720 |access-date=2016-09-25 |website=www.scottaaronson.com}}</ref>

A simple example of an NP-hard problem is the [[subset sum problem]].

Informally, if ''H'' is NP-hard, then it is at least as difficult to solve as the problems in [[NP (complexity)|NP]]. However, the opposite direction is not true: some problems are [[Undecidable problem|undecidable]], and therefore even more difficult to solve than all problems in NP, but they are probably not NP-hard (unless P=NP).<ref>{{Cite web |title=Is undecidable(complement of R) a subset of NP-hard? |url=https://cs.stackexchange.com/q/7676/1342 |access-date=2024-02-09 |website=Computer Science Stack Exchange |language=en}}</ref>

== Definition ==
A [[decision problem]] ''H'' is NP-hard when for every problem ''L'' in NP, there is a [[Many-one reduction|polynomial-time many-one reduction]] from ''L'' to ''H''.<ref name="Leeuwen"/>{{rp|80}}

Another definition is to require that there be a polynomial-time reduction from an [[NP-complete]] problem ''G'' to ''H''.<ref name="Leeuwen"/>{{rp|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, and it also includes [[search problem]]s or [[optimization problem]]s.

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

Some NP-hard optimization problems can be polynomial-time [[Approximation algorithm|approximated]] up to some constant approximation ratio (in particular, those in [[APX]]) or even up to any approximation ratio (those in [[Polynomial-time approximation scheme#As a complexity class|PTAS]] or [[Polynomial-time approximation scheme#Deterministic|FPTAS]]). There are many classes of approximability, each one enabling approximation up to a different level.<ref>{{Cite journal |last1=Escoffier|first1=B.|last2=Paschos|first2=B.Th.|year=2010|title=A survey on the structure of approximation classes|journal=Computer Science Review|volume=4|issue=1|pages=19–40}}</ref> 

== Examples ==
All [[NP-completeness|NP-complete]] problems are also NP-hard (see [[List of NP-complete problems]]). For example, the optimization problem of finding the least-cost cyclic route through all nodes of a weighted graph&mdash;commonly known as the [[travelling salesman problem]]&mdash;is NP-hard.<ref>{{citation|first1=E. L.|last1=Lawler|author1-link=Eugene Lawler|first2=J. K.|last2=Lenstra|author2-link=Jan Karel Lenstra|first3=A. H. G.|last3=Rinnooy Kan|first4=D. B.|last4=Shmoys|title=The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization|year=1985|publisher=John Wiley & Sons|isbn=0-471-90413-9|url-access=registration|url=https://archive.org/details/travelingsalesma00lawl}}.</ref> The [[subset sum problem]] is another example: 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.

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 problem|undecidable]]. There are also NP-hard problems that are neither ''NP-complete'' nor ''Undecidable''. For instance, the language of [[true quantified Boolean formula]]s is decidable in [[PSPACE|polynomial space]], but not in non-deterministic polynomial time (unless NP = [[PSPACE]]).<ref>More precisely, this language is [[PSPACE-complete]]; see, for example, {{citation|title=Complexity Theory: Exploring the Limits of Efficient Algorithms|first=Ingo|last=Wegener|publisher=Springer|year=2005|isbn=9783540210450|page=189|url=https://books.google.com/books?id=1fo7_KoFUPsC&pg=PA189}}.</ref>

== 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 theory|computational complexity]], it is used as the basis of several classes:
;[[NP (complexity)|NP]]: Class of computational decision problems for which any given ''yes''-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 decision 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.
;[[NP-equivalent]]: Decision problems that are both NP-hard and NP-easy, but not necessarily in NP.
;[[NP-intermediate]]: If P and NP are different, then there exist decision 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 because in this case every NP-complete problem would fall in P, and by definition, every problem in NP can be reduced to an NP-complete problem.)

== Application areas ==
NP-hard problems are often tackled with rules-based languages in areas including:
* [[Approximate computing]]
* [[Configuration management|Configuration]]
* [[Cryptography]]
* [[Data mining]]
* [[Decision support system|Decision support]]
* [[Phylogenetics]]
* [[Planning]]
* Process monitoring and control
* Rosters or schedules
* Routing/vehicle routing
* [[Schedule|Scheduling]]

== NP-hard problems ==
Problems that are decidable but not [[NP-completeness|NP-complete]], often are optimization problems:

* [[Knapsack problem|Knapsack optimization problems]]
* [[Integer programming]]
* [[Travelling salesman problem|Travelling salesman optimization problem]]
* [[Vertex cover|Minimum vertex cover]]
* [[Clique problem|Maximum clique]]
* [[Hamiltonian path problem|Longest simple path]]
* [[Graph coloring]]; an application: register allocation in compilers

==See also==
* [[Lists of problems]]
* [[List of unsolved problems]]
* [[Reduction (complexity)]]
* [[Unknowability]]

== References ==
{{reflist}}
*{{Garey-Johnson}}

{{ComplexityClasses}}

{{DEFAULTSORT:Np-Hard}}
[[Category:NP-hard problems| ]]
[[Category:Complexity classes]]