A Solution of the P versus NP Problem?

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.

[ Parent | on HN ]

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)

[ Parent | on HN ]

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?

[ Parent | on HN ]

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)

[ Parent | on HN ]