4 ms·

I just read up on this. If what I read is true, TSP is NP-hard not NP complete. You can’t trivially prove that the solution is optimum. Reference: https://ekli

• thaumasiotes 7y ago
  There is a conversion between the decision problem I mentioned ("is there a path of length less than some fixed L?") and the general problem "what is the minimum path length?". If a solution exists, it will have length less than or equal to the product of (1) the maximum edge cost and (2) the number of nodes in the graph.[1] You can then find the actual minimum length by doing a binary search on the threshold below which there is no solution. And it's very easy to show that the decision problem is in NP -- given a candidate path, it is trivial to verify that its cost is less than a constant L. So we have the results that (1) the decision problem is NP-complete; (2) the general problem can be solved in polynomial time if you can solve the decision problem in polynomial time. That's enough to show the general problem is NP-complete. [1] Under the assumption that the graph is complete and has no edges of infinite cost. Without that assumption, multiply (1) the maximum finite edge cost; (2) the number of finite-cost edges in the graph; (3) the number of nodes in the graph.