4 ms·
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 flawe
by hexomancer 9y ago
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/no_the_tsp_isn_t_np_complete?lang=en 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.
- mihaild 9y agoDecision 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)
- hexomancer 9y agoDo you have a reference to a reputable source that proves the optimization version is cook-reducable to decision version?
- mihaild 9y agoI don't. (it's always hard to find reference for easy problems)