Hacker News Reader

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)

View on HN

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)

Reply on news.ycombinator.com