How is TSP NP-Hard?
I read the following in one of the answer on SO :
The Traveling Salesman Problem, as normally posed, is to find the cheapest route connecting all cities. That isn't a decision problem, and we can't verify any proposed solution directly. We can restate it as a decision problem: given a cost C, is there a route that's cheaper than C? This problem is NP-complete, and with a little work we can solve the original TSP about as easily as the modified, NP-complete, form. Therefore, the TSP is NP-hard, since it's at least as hard as an NP-complete problem.
I understand that a TSP is NP-Complete but how the problem is NP-Hard ? I read that problems that are in NP but not in P are NP-Hard. I cannot relate this thing to the TSP . Please explain this.
Answer
NP-Hard problems are those problems for which every problem in NP has a polynomial time (Cook or Karp, multiple definitions) reduction to. These could contain problems which are not in NP and in fact need not even contain decideable problems (like the Halting problem).
NP-Complete problems are those problems in NP which are also NP-Hard.
If P is not equal to NP, then there are infinitely many problems in NP which are neither in P, nor NP-Complete (Ladner's theorem).