4 ms·
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 t
by mihaild 9y 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)
- hexomancer 9y agoDo you have a reference to a reputable source that proves the optimization version is cook-reducable to decision version?
- mihaild 9y agoI don't. (it's always hard to find reference for easy problems)