News for hackers. Stuff that matters.

A comment on A Solution of the P versus NP Problem?. Parent comment

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 ]