3 ms·
There is no debate, plain travelling salesman is defiantly not known to be NP-complete. The usual solution for optimisation problems is to turn them into a deci
by CJefferson 11y ago
There is no debate, plain travelling salesman is defiantly not known to be NP-complete. The usual solution for optimisation problems is to turn them into a decision problem, by saying "is there a path of length k or less?". Then it is in NP-complete
- nsnick 11y agoSo yeah in the video, traveling salesman should not have been included in NP
- ColinWright 11y ago> There is no debate, plain travelling salesman > is defiantly not known to be NP-complete. Actually, there is no debate, plain TSP is specifically not NP-complete and cannot be, because it's not a decision problem. So it's not just, as you say, "not known to be" but instead is "known not to be". However, by using binary search you can convert a decision version of TSP into the optimisation version in polynomial time. In this sense it is perfectly reasonable to refer to TSP as being NP-Complete. I agree completely that these sorts of differences actually matter when dealing with the technicalities, but in practice it makes sense not to worry too much when trying to explain the broader concepts.