title: How is TSP NP-Hard?
body: <p>I read the following in one of the answer on <a href="https://stackoverflow.com/questions/3671429/why-are-np-problems-called-that-way-and-np-hard-and-np-complete">SO :</a></p>
  
  <p><em>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.</em></p>
  
  <p>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. </p>