In comp.theory Nimmi Srivastav <firstname.lastname@example.org> wrote:
> email@example.com wrote: >> clearing up. A problem is NP-hard if every problem in NP reduces to >> it ("reduce" here typically means polytime Karp reduction, but slight >> variants on this definition are also seen sometimes in the literature).
> Thanks to all of you who responded. A lot of my doubts have been > removed, courtesy all of you. However, there is one doubt that > remains. This pertains to the following claim:
> A problem is NP-hard if every problem in NP reduces to it
> Now, the Halting Problem is unsolvable. It is also NP-hard. This > means that any problem in NP reduces to the Halting Problem. How can > any solvable problem (albeit with an inefficient algorithm) be reduced > to an unsolvable problem? It sounds somewhat counter-intuitive on the > surface.
Consider the following simple program to solve the decision version of the travelling salesman problem:
for each permutation of cities if cost of permutation is less than min_cost min_cost=cost of permutation while (min_cost > K);
First do a brute force search of all possible permutations to find the minimum. Then enter an infinite loop if the minimum cost is greater than K, otherwise exit.
This program halts if the minimum tour has a cost of K or less, and loops otherwise. If we could solve the halting problem in polynomial time, then we could determine if there existed a tour of cost K or less in polynomial time.