Let Nature Solves NP-Complete Problem

An Anonymous Coward writes: "Why not? Here's a start: Tourist Map Illuminates shortest route Light up a gas-tube graph with electricity to find the shortest path between two points. Can they extend this to multiple vertices to instantly solve the NP-Complete traveling salesman problem?"

Comments

Knotted String and Dijkstra

[alacqua]

Here's two other amazing solutions. Knotted string and Dijkstra's algorithm.

There are several methods that can be used to solve this problem. One way is to make a model of the map by knotting together pieces of string whose lengths are proportional to the lengths of the roads. To find the shortest path, take hold of the knots corresponding to A and L - and pull tight!
-Introduction to Graph Theory, Robin J. Wilson

How can we find the shortest route from one location to another?... Dijkstra's Algorithm (Dijkstra [1959] and Whiting-Hillier [1960]) solves this problem quickly,...
-Introduction to Graph Theory, Douglas B. West

Check any book on graph theory or on algorithms for the details of Dijkstra's algorithm.

The setup with the tourist map is kind of cool but hardly a breakthrough for math or computer science.