P =/!= NP? Travelling Salesman Problem (Updated Nov 7, 2009)
Friday, 6. November 2009, 02:06:37
The travelling salesman problem (TSP) is where you try to find the shortest route when visiting N number of towns. Apparently, the decision version of this problem, if solved in polynomial time, would be a solution to an NP-complete problem and would also solve all other NP-complete problems in polynomial time. Not only that, but since you can use binary search in O(log(n)) time when used with the decision version of TSP, finding the shortest distance up to X digits of precision would likewise be done in polynomial time.
My first attempt was to first build a convex hull around all the cities (points). A nice property of this is that if all points are part of the convex hull, then you have the shortest path.
My first attempt was to first build a convex hull around all the cities (points). A nice property of this is that if all points are part of the convex hull, then you have the shortest path.
WIDGETIZE