Slashdot Mirror
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?"
This just goes to show you that not ALL high-tech elegant solutions require digital circuitry.
utter rubbish
... if finding the shortest route between 2 points on a network was actually an NP-Complete problem
...here
-- SIGFPE
... for computers too. Any decent book on algorithms will give you several elegant, easy-to-implement, blazingly fast methods. The TSP, like all NP problems, is much different. Thinking about the gas-tube device (which is a really cool idea, I must say) there's no way to apply it to the TSP. Electricity just doesn't work that way.
The correlation between ignorance of statistics and using "correlation is not causation" as an argument is close to 1.
But it's the simplicity of the solution that makes it so elegant. Why say more when so little is enough?
Yours Sincerely, Michael.
i'd like to think technology can do more than make maps for tourists. :)
It is kindof neat that someone had this idea and produced a working model (pictures, anyone?) But by the time a skilled laborer builds a piece of equipment which solves the problem, a computer will have computed the solution a few billion times over, including the time it took to program and input the problem.
;-)
Furthermore it doesn't solve the problem satisfactorily, for instance how do you make a one way street in a neon tube? How do you post speed limits for electrons?
There may be solutions to these questions, and more, but the computer will still solve all these problems more quickly than any person or group of people can build a device which can do so.
The larger question of whether nature can provide solutions to unsolved problems is, of course, a resounding yes. But we've known that for awhile, what's new? The problem is translating the question into a form nature can handle, then interpretig the results. As we come ever closer to biological computers we will have a better grasp of performing such experiments - the question is whether quantum computers will come first (which apparently solve every NP problem - according to the optomistic physicists, anyway
-Adam
First, shortest path algorithms do NOT consider every possible route. Instead, they consider the best extention to an already known shortest path (starting with the shortest path to the beginning, which is obviously 0). [roughly -- Dijsktra's algorithm is slightly more complicated, but not much].
Second, if the number of operations increases polynomially, how does the problem get classified as NP complete? Never mind the fact that a lower bound alone is not enough to put a problem in a specific class, if the complexity is actually O(n^2), then the problem is clearly in P, not NP.
Other than a nice hack, this article does not describe any important breakthrough.
From my physics classes, I recall that electricity follows the line of least resistance.
Now, this means at every crossroad, the electron flow will select the road with the least electric resistance.
This leads to a kind of greedy algorithm, that possibly leads to a good approximation of the shortest path, but still an approximation.
Or does the current flow path oscillate to find the absolute resistance minimum, so it does not get stuck in a relative minimum?
Or do I miss something?
There was a paper in Science a few years back that took a similar approach.
I don't have the references any more (but here is a similar source), but here's the gist: They built strands of RNA with specific sites being mapped to parts of the travelling salesman solution, replicated those strands billions of times with PCR. and mixed well. The reactions that prevaled were logically the "shortest" path.
Nature abounds with massively parallel computing engines.
"It is our blasphemy which has made us great, and will sustain us, and which the gods secretly admire in us." - Zelazny
it's called leinthal's paradox -- the cost is NOT O(n^2) the cost is O((n-1)!) (http://konf2.ims.ac.jp/review/sec4.html)r a's algorithm merely simplifies the correct procedural solution by limiting the sample space (which introduces a possibility of error) -- it APPROXIMATES the solution because the exact calculation is NP-Complete... another reference: here
Djikst
--Ks9
Just in case you're not trolling... Dijkstra gives a complete solution to the shortest path algorithm in O(n^2) time (actually I believe there are O(n log n) implementations). This has nothing whatsoever to do with the travelling salesman algorithm. They are two completely different problems.
No.
This resistance-path method will only find the shortest path from one point to another -- a task for which there already exist solutions which can complete in polynomial time. A *full* path (which is required as a solution to the Travelling Salesman problem) is not directly solved by this method.
TANSTAAFI: There Ain't No Such Thing As A Free iPod.
I am being stupid and talking out of my ass, the original post was about the Travelling salesman problem, which is npc... and I misread your post as being about the main post being non-npc -- i.e. this whole conversation was line noise. my bad.
let's reiterate - traveling salesman: np-complete
shortest path between two arbitrary points in a graph of n points - O(n^2)
/me should go get some more caffeine
--Ks9
These devices wouldn't apply to a neon tube in nearly the same way.
You couldn't model the map as a circuit since current would flow through as all of the circuit - you might be able to glean some information from the current in each road, but then you're still executing a search.
The helium tube is an instantaneous solution, but putting resistors and diodes in the tube wouldn't work since you're dealing with much higher voltages and lower currents.
-Adam
Yeah, I remember something about figuring out where to build factories by drilling holes in a map and hanging wieghts on strings dropped through the holes, and the whole thing would settle out with the factory in the optimal location (barring awkwardly placed rivers and whatnot).
This next song is very sad. Please clap along. -- Robin Zander
From http://www.csc.liv.ac.uk/~ped/teachadmin/COMP202/a nnotated_np.html -- a list of selected np-complete problems
Number: 27
Name: Travelling Salesman [ND22] 3-4
Input: A set C of n cities {c1,...,cn}; for each pair of cities (ci,cj) (1
Question: Is there an ordering of the n cities such that the value sum from i=1 to n-1 dpi(i),pi(i+1)+dpi(n),pi(1) is no more than B?
Comments: In effect what this problem is asking is whether there is a tour of the given collection of cities that visits each city exactly once and takes up total distance no more than B. There is a huge volume of literature concerning approximation methods, search heuristics, special case methods, etc for this very well studied problem. A bibliography has been compiled.
--Ks9
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.
Move on. There's nothing to see here.
Theres many algorithms for finding shortest path, fromsimple bradth first/depth first through steepest ascent hill climbing, to ones that estimate remaining distance, to routing tables, and of course dijiska
I'd just like to point out that this is not the traveling salesman problem. This is the shortest point between any two points, not all points on the map. Read the article.
If it's for-profit but free, you're not the customer -- you're the product (e.g., the Slashdot Beta's "audience").