Re:A Solution of the P versus NP Problem?
by hexomancer on Monday August 14, 2017 @05:29PM
(#15013109)
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)
Re:A Solution of the P versus NP Problem?
by hexomancer on Tuesday August 15, 2017 @02:27AM
(#15015983)
Do you have a reference to a reputable source that proves the optimization version is cook-reducable to decision version?
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.