News for hackers. Stuff that matters.
Re:Ant Colony Optimization Visualization for the Travelling ... by LeonB on Friday December 13, 2019 @08:40AM (#21781398)
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://eklitzke.org/the-traveling-salesman-problem-is-not-n...

Re:Ant Colony Optimization Visualization for the Travelling ... by thaumasiotes on Friday December 13, 2019 @08:49AM (#21781453)
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.