Editing NP-hardness (section)

== 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>