4 ms·
Yes. TSP is NP-complete, which means that exact solutions to TSP can be turned into exact solutions to any other NP problem in P time. However, there is no guar
by pavpanchekha 12y ago
Yes. TSP is NP-complete, which means that exact solutions to TSP can be turned into exact solutions to any other NP problem in P time. However, there is no guarantee on how this transformation behaves on non-exact solutions. In fact, there are many problems that are known to be non-approximable. For example, Vertex Cover is known not to have approximation algorithms better than a factor of 1.3 or so (assuming P != NP). Maximum clique is completely inapproximable (it is impossible to approximate it to any constant factor).