Hacker News new | ask | show | jobs
by mihaild 3230 days ago
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)
1 comments

Do you have a reference to a reputable source that proves the optimization version is cook-reducable to decision version?
I don't. (it's always hard to find reference for easy problems)