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
If you like walking over buildings!
that 5 sentence blurb was the whole article? Seems like a fascinating solution to a problem, surely someone could have written another 3 or 4 sentences.
no mention of how this could apply to programmable MEMS or anything, and this is EE Times, odd.
...here
-- SIGFPE
This doesn't strike me as all that impressive. They need to customize hardware for any city they wish to model. One can consider this to be a form of preprocessing, and for a fair comparison to be made, one must also allow preprocessing to be done using the computational method. After preprocessing, results can be obtained using an array lookup.
This may be interesting, but I doubt it's all that revolutionary.
... 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.
The travelling salesman finds the shortest path through a graph visiting every point exactly once... computationally one must try every possibility of routes in order to find the path with the least cost... which increases polynomially with respect to the number of points on the graph ... classifying it as NP-Complete. What I don't understand is how this is actually a solution to this problem since wouldn't multiple electrodes trace a path to another electrode even if it was already connected? Therefore invalidating the solution by the definition (where the shortest path hits each point exactly ONCE)
--Ks9
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.
It was hard. Would someone please teach the EE Times how to write without using dashes. And it's not exactly information filled. For example what if two paths are equidistant. The claim at the beginning that it could lead to a new class of computers without any justification left my head spinning, making the rest of the article even harder to digest.
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
There was a neat Scientific American article about twenty years ago about fast analog solutions to hard problems.
The example that sticks in my mind was sorting numbers with dry spaghetti, where the spaghetti was broken at a lenght that represented the size of the number. If you hold the spaghetti vertically in a column and touch the top you will have selected the largest number. Iterate until numbers are sorted from greatest to least. You have a linear time sorting algorithm.
They also had a factoring machine.
Unfortunately, all of these solutions lose big on setup time. Building the analog solving tools is generally difficult, and becomes difficult faster than standard mathematical methods. I suspect this may be universal.
Assembly is the reverse of disassembly.
Electricity will only find the shortest path. This is an n^2 operation. Maybe it does it faster than that, but it is an n^2 operation with computers, which is pretty cheap.
The travelling salesman problem on the other hand, which is not what the article talks about, imposes additional constraints: the path must visit all nodes and it must form a cycle (ie end where it began). These additional constraints are what make this an NP-complete problem. But unless the article is missing critical information, they have not found a way to impose those constraints.
The links you mention are about the TSP, not the shortest path problem.
the 'additional' constraints are the elements that comprise the travelling salesman problem... n^2 is for the dijkstra algorithm, again, an approximation of the correct solution without checking the total problem space... you seem to be misinformed, have you ever taken a course in combinatorics?
--Ks9
Furthermore it doesn't solve the problem satisfactorily, for instance how do you make a one way street in a neon tube?
Diodes (allows current to flow only one way)
How do you post speed limits for electrons?
Resistors (regulates the flow of current more than the speed -- but you get the idea)
It is O(n log n)
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
no text
--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
Does you wants to fixed them grammatical error in those heading?
: Fruitbat :
which increases polynomially with respect to the number of points on the graph ... classifying it as NP-Complete.
WHAT? This has nothing to do with NP-Completeness. A problem A is NP complete iff it is NP and for all problems B in NP, B can be reduced to to A in polynomial time. (this means you can convert any problem in NP to an NP-Complete problem in polynomial time and the solution to B can be determined by running an input on A)
So unless you can show this your claim about np completeness is complete bull.
If religous zealots don't believe in Evolution, then why are they so worried about bird flu?
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 thought NP-Completeness referred to computational solutions. I mean, what's the complexity of that gas solution? Could the gas device be considered a really fast computer that tries out the full 2^n possibilities really quick?
Or else the solution of every NP-Complete problem could be "Ask a really smart guy". If I could ask some Autistic guys to find the 3-color of a graph for me would that make the problem Big-Theta of 1?
P.S. Don't yell at me, I'm not smart.