firstname.lastname@example.org 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.