News for hackers. Stuff that matters.
Re:A Solution of the P versus NP Problem? by mihaild on Monday August 14, 2017 @05:17PM (#15013003)
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.

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.

Re:A Solution of the P versus NP Problem? by mihaild on Monday August 14, 2017 @05:39PM (#15013209)
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?
Re:A Solution of the P versus NP Problem? by mihaild on Tuesday August 15, 2017 @02:44PM (#15021106)
I don't. (it's always hard to find reference for easy problems)