Suppose I have a weighted graph G=(V, E), where V the set of nodes are locations (for instance cities) and E the set of edges are possible travel routes between the locations with the weight being the distance.

Suppose we are given a path P between two arbitrary nodes a, b in V. Come up with a method to check if the path is optimal (lowest possible distance) where the number of steps required for the method is asymptotically polynomial with respect to the number of nodes. Alternatively prove that no such polynomial time method exists. (Note: If you solve this you can win 1 million dollars)

Question

Suppose I have a weighted graph G=(V, E), where V the set of nodes are locations (for instance cities) and E the set of edges are possible travel routes between the locations with the weight being the distance.

Suppose we are given a path P between two arbitrary nodes a, b in V. Come up with a method to check if the path is optimal (lowest possible distance) where the number of steps required for the method is asymptotically polynomial with respect to the number of nodes. Alternatively prove that no such polynomial time method exists. (Note: If you solve this you can win 1 million dollars)

anonymous · Answer

I know this probably belongs in computer science but that section is empty :P

anonymous · Answer

Hint: This is actually a millennium prize problem.

ganeshie8 · Answer

looks like minimum spanning tree / salesman problem  - NP-complete

anonymous · Answer

Yeah its the TSP decision problem which is indeed NP-complete

ganeshie8 · Answer

only aliens can solve this in P i think :P if there is a method for solving this in P, then all other problems in this list can also be solved in P http://en.wikipedia.org/wiki/List_of_NP-complete_problems