3

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.

Community
  • 1
  • 1
Suhail Gupta
  • 22,386
  • 64
  • 200
  • 328

2 Answers2

7

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).

Trixter
  • 109
  • 3
  • I know by definition what does NP-Hard mean ! I have mentioned in the question _"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"_ – Suhail Gupta Nov 03 '12 at 05:55
  • 1
    @SuhailGupta: You cannot relate to it, because what you read is _wrong_. See the last sentence of the answer. – Trixter Nov 03 '12 at 06:07
  • @SuhailGupta: Saw your link to the SO question. Where exactly does it say "problems that are in NP but not in P are NP-Hard."? Also note that the last sentence was missing a couple of words which I have now added. – Trixter Nov 03 '12 at 06:52
3

The optimization version of TSP problem has been shown NP-hard, but yet known whether it's in NP or not since there is yet known verification algorithms.

The decision version of the TSP problem has been shown NP-complete (both in-NP and NP-hard).

CrepuscularV
  • 983
  • 3
  • 12
  • 25
  • what is the difference between the optimisation and decision versions? – MTA May 23 '17 at 14:40
  • @RegUser optimization version looks for an answer for what is the minimum cost? To verify that, we need to check every route and it is not in polynomial time. The decision version is, is there any route which is shorter than cost K. We can verify the last one in polynomial time – PeerNet May 21 '19 at 01:07
  • @MTA - The Result. Decision=Boolean or Optimization=numeric. – pds Dec 13 '22 at 09:42