Hacker News Reader

Epsilon isn't a problem, as TSP is NP-complete even for integer weights. Your solution needs some modification for case where we have multiple optimal cycles (as you will find edges that are included in at least one cycle).

I don't think there is anything wrong with optimization been reducible to decision - it's quite common method both in theory and in practice.

View on HN

I didn't say there is anything wrong with reducing the optimization to decision in general. But I feel this specific application to the TSP problem may be flawed. (for the reasons i mentioned before. i.e wikipedia being very specific about the decision version) For another resource see: https://www.ibm.com/developerworks/community/blogs/jfp/entry...

note: I am not implying that the above source is reputable. But it does hint that the solution to this problem probably is not this trivial.

Decision version of TSP is NP-complete. Optimization version is Cook-reducible to decision version of TSP. And it problem is Cook-reducible to P-problem, then the problem is itself in P. (note that it's not true if you replace P with NP, for example)

Do you have a reference to a reputable source that proves the optimization version is cook-reducable to decision version?

I don't. (it's always hard to find reference for easy problems)

Reply on news.ycombinator.com