5 ms·

Oil Drop Navigates Complex Maze

23 points by icey 17y ago

bioweek 17y ago
Wait, so if this oil drop is solving an NP complete problem in N time, couldn't we map other NP complete problems onto a maze, and have the oil drop solve them for us?
- jws 17y ago
  Shortest path from one point to another in a graph is polynomial. Shortest path to all nodes is NP complete.
  - ondra 17y ago
    No, all-pairs shortest path problem is in P as well.
    - jws 17y ago
      I spoke too loosely. Shortest path traversing all nodes is NP (traveling salesman). Obviously shortest path between each pair of nodes is going to be polynomial since the number of pairs is polynomial.
  - elblanco 17y ago
    That's not right at all. Dijkstra's for example computes a minimum spanning tree on a graph (it doesn't really compute shortest path from a->b, it computes shortest path from a to all other nodes) and does it in O(E+VlogV) if I remember....which is quite a bit better than polynomial time.
- chime 17y ago
  1. Shortest Path is NP complete? 2. Who says this is in N time?
- dkarl 17y ago
  The acid gradient provides extra information, which changes the complexity of the problem.
- jerf 17y ago
  While there is widespread belief that physical processes can solve NP-complete problems, there isn't actually any evidence. Physical processes can get stuck in local optima, which is another way of saying that they fail to solve the NP-complete problem you hand them. Here's an account of someone who actually tried one in real life (it takes a couple of pages): http://www.scottaaronson.com/papers/npcomplete.pdf http://www.scottaaronson.com/papers/npcomplete.pdf Personally I see no reason to believe this isn't true of all physical processes that "solve" an NP-complete problem.
- koningrobot 17y ago
  Actually, in this experiment, you could say the acid does a breadth-first search through the maze. When it finds the entrance, the oil droplet starts moving through the path that the acid found. So the droplet is merely a distractor; the acid is doing all the NP work.
icefox 17y ago
Hmm, could this be exploited in some way to find the longest path?
- phaedrus 17y ago
  Actually your question perfectly illustrates the limitations of thinking of this as a computation device: I doubt it could be used to find the longest path, for the reason that whatever way the oil droplet responds at one intersection, it will employ the same type of response at the next. The oil droplet is able to (usually) find the shortest path by always moving in the direction of higher acid content. Would you expect it to find the longest path by always going away from the higher acid content? That's wrong; that's not the longest path to the exit, it's the SHORTEST path back to the entrance! OK, so how about the least acidic path that it hasn't already taken; i.e. not allow it to double back? Also wrong: that will lead it into the first blind alley that faces away from the exit, where it will be trapped. So given that 1. We cannot use the highest acidic value as a criterion and 2. We cannot use the lowest acidic value as a criterion and 3. We cannot use the lowest acidic value not already visited, that leaves us with expecting the droplet to neither always take the most acidic exit from an intersection nor the least acidic. However, surely SOMETIMES the least acidic exit might be the longer path, and SOMETIMES the most acidic exit is. Then we are forced to conclude that the droplet must act differently at different times with the same stimulus! That implies it has to maintain some kind of state, or memory. As the droplet is undifferentiated oil, it seems unlikely that it has a large enough state space to solve the longest path problem.
kaddar 17y ago
His claims about np-completeness implies that his research needs to be seriously questioned.
- hendler 17y ago
  The quote was: "Computers and mathematics could also benefit. Maze navigation can fall into a class of problems known as NP-complete, "which computers have a surprisingly hard time solving, as the effort to solve them goes up exponentially with the scale of the problem," says chemist Irv Epstein of Brandeis University in Waltham, Massachusetts. "The kind of approach shown here with these mazes might be a very efficient approach to address this problem." There are other cases of analog chemical processes beating out digital computations. But the reference to medicine also seems like a stretch - navigating a simple maze with a couple of acidic and basic chemicals seems very far away from a complex chemical hunting cancer in the human body.
  - Groxx 17y ago
    Clearly, given varied acidic / basic areas in human bodies, this is not a "magic bullet" that'll only target cancer cells. They're also not claiming that this is the case (though the wording is quite vague). At best, it'll increase the concentration of a drug in the cancer (among other places) above that of a "plain" drug, which is an improvement, thus should be investigated.
- wynand 17y ago
  I don't see anything in the article that shows that he made the statement about NP-completeness. It seems that the quoted chemist made that statement. For someone who's not a graph theorist, it's an easy mistake to make, since the longest path problem is, in general, NP-complete. He was probably just thinking of this problem.
  - wynand 17y ago
    I just downloaded his article, and he states that "With the advent of computers, algorithms for maze solving have become automated, but the solution times still scale unfavorably with maze size/complexity" and then references a paper by Dijkstra (Dijkstra, E. W. Numer. Math. 1959, 1, 269.). That might be true for dense graphs, if you think that O(|V|^2 log|V|) is unfavourable. A normal maze graph is planar and therefore |V| <= 3|E| - 6. Thus, maze problems can always be solved in O(|V| log|V|) time for a constant number of exits and starting points. So, while the author made a little mathematical blunder ( single layer maze problems are efficient to solve), he's not the one that implied NP-completeness. EDIT: Clarified my comment so that no-one can think I'm implying that an O(|V|^2 log|V|) algorithm is an NP problem.
charltones 17y ago
This bears a striking resemblance to the HN posting on antiobjects: http://news.ycombinator.com/item?id=981738 http://news.ycombinator.com/item?id=981738 (representing a pac-man game by having ghosts detect a "smell" of pac-man that diffuses through the maze)
- icefox 17y ago
  This is of course the Ant Colony Optimization paper from 91 http://en.wikipedia.org/wiki/Ant_colony_optimization http://en.wikipedia.org/wiki/Ant_colony_optimization
phaedrus 17y ago
Consider this: replace "acid gradient" in the experiment description with "air pressure": Imagine constructing a larger version of this maze from cardboard. A vacuum cleaner is placed at the exit of the maze. Sucking the air out of the maze creates a pressure gradient such that there is higher air pressure nearer the entrance and lower air pressure nearer the exit. This pressure gradient causes the ping pong ball to roll through the maze to exit. This is a brilliant application of a novel idea BUT the physical process at work only seems miraculous because we do not deal with acid gradients every day. Consider: would the same claims that it "performs a computation" be as credible in the vacuum cleaner and air pressure version? If any computation is being done, it is a search space being covered in parallel by billions of independent agents (the molecules of the medium). The movement of the water droplet (or ping pong ball!) merely serves to display the answer.

23 points by icey 17y ago

Wait, so if this oil drop is solving an NP complete problem in N time, couldn't we map other NP complete problems onto a maze, and have the oil drop solve them for us?

jws 17y ago
Shortest path from one point to another in a graph is polynomial. Shortest path to all nodes is NP complete.
- ondra 17y ago
  No, all-pairs shortest path problem is in P as well.
  - jws 17y ago
    I spoke too loosely. Shortest path traversing all nodes is NP (traveling salesman). Obviously shortest path between each pair of nodes is going to be polynomial since the number of pairs is polynomial.
- elblanco 17y ago
  That's not right at all. Dijkstra's for example computes a minimum spanning tree on a graph (it doesn't really compute shortest path from a->b, it computes shortest path from a to all other nodes) and does it in O(E+VlogV) if I remember....which is quite a bit better than polynomial time.
chime 17y ago
1. Shortest Path is NP complete? 2. Who says this is in N time?
dkarl 17y ago
The acid gradient provides extra information, which changes the complexity of the problem.
jerf 17y ago
While there is widespread belief that physical processes can solve NP-complete problems, there isn't actually any evidence. Physical processes can get stuck in local optima, which is another way of saying that they fail to solve the NP-complete problem you hand them. Here's an account of someone who actually tried one in real life (it takes a couple of pages): http://www.scottaaronson.com/papers/npcomplete.pdf http://www.scottaaronson.com/papers/npcomplete.pdf Personally I see no reason to believe this isn't true of all physical processes that "solve" an NP-complete problem.
koningrobot 17y ago
Actually, in this experiment, you could say the acid does a breadth-first search through the maze. When it finds the entrance, the oil droplet starts moving through the path that the acid found. So the droplet is merely a distractor; the acid is doing all the NP work.

icefox 17y ago

Hmm, could this be exploited in some way to find the longest path?

phaedrus 17y ago
Actually your question perfectly illustrates the limitations of thinking of this as a computation device: I doubt it could be used to find the longest path, for the reason that whatever way the oil droplet responds at one intersection, it will employ the same type of response at the next. The oil droplet is able to (usually) find the shortest path by always moving in the direction of higher acid content. Would you expect it to find the longest path by always going away from the higher acid content? That's wrong; that's not the longest path to the exit, it's the SHORTEST path back to the entrance! OK, so how about the least acidic path that it hasn't already taken; i.e. not allow it to double back? Also wrong: that will lead it into the first blind alley that faces away from the exit, where it will be trapped. So given that 1. We cannot use the highest acidic value as a criterion and 2. We cannot use the lowest acidic value as a criterion and 3. We cannot use the lowest acidic value not already visited, that leaves us with expecting the droplet to neither always take the most acidic exit from an intersection nor the least acidic. However, surely SOMETIMES the least acidic exit might be the longer path, and SOMETIMES the most acidic exit is. Then we are forced to conclude that the droplet must act differently at different times with the same stimulus! That implies it has to maintain some kind of state, or memory. As the droplet is undifferentiated oil, it seems unlikely that it has a large enough state space to solve the longest path problem.

kaddar 17y ago

His claims about np-completeness implies that his research needs to be seriously questioned.

hendler 17y ago
The quote was: "Computers and mathematics could also benefit. Maze navigation can fall into a class of problems known as NP-complete, "which computers have a surprisingly hard time solving, as the effort to solve them goes up exponentially with the scale of the problem," says chemist Irv Epstein of Brandeis University in Waltham, Massachusetts. "The kind of approach shown here with these mazes might be a very efficient approach to address this problem." There are other cases of analog chemical processes beating out digital computations. But the reference to medicine also seems like a stretch - navigating a simple maze with a couple of acidic and basic chemicals seems very far away from a complex chemical hunting cancer in the human body.
- Groxx 17y ago
  Clearly, given varied acidic / basic areas in human bodies, this is not a "magic bullet" that'll only target cancer cells. They're also not claiming that this is the case (though the wording is quite vague). At best, it'll increase the concentration of a drug in the cancer (among other places) above that of a "plain" drug, which is an improvement, thus should be investigated.
wynand 17y ago
I don't see anything in the article that shows that he made the statement about NP-completeness. It seems that the quoted chemist made that statement. For someone who's not a graph theorist, it's an easy mistake to make, since the longest path problem is, in general, NP-complete. He was probably just thinking of this problem.
- wynand 17y ago
  I just downloaded his article, and he states that "With the advent of computers, algorithms for maze solving have become automated, but the solution times still scale unfavorably with maze size/complexity" and then references a paper by Dijkstra (Dijkstra, E. W. Numer. Math. 1959, 1, 269.). That might be true for dense graphs, if you think that O(|V|^2 log|V|) is unfavourable. A normal maze graph is planar and therefore |V| <= 3|E| - 6. Thus, maze problems can always be solved in O(|V| log|V|) time for a constant number of exits and starting points. So, while the author made a little mathematical blunder ( single layer maze problems are efficient to solve), he's not the one that implied NP-completeness. EDIT: Clarified my comment so that no-one can think I'm implying that an O(|V|^2 log|V|) algorithm is an NP problem.

charltones 17y ago

This bears a striking resemblance to the HN posting on antiobjects: http://news.ycombinator.com/item?id=981738 http://news.ycombinator.com/item?id=981738 (representing a pac-man game by having ghosts detect a "smell" of pac-man that diffuses through the maze)

icefox 17y ago
This is of course the Ant Colony Optimization paper from 91 http://en.wikipedia.org/wiki/Ant_colony_optimization http://en.wikipedia.org/wiki/Ant_colony_optimization

phaedrus 17y ago

Consider this: replace "acid gradient" in the experiment description with "air pressure": Imagine constructing a larger version of this maze from cardboard. A vacuum cleaner is placed at the exit of the maze. Sucking the air out of the maze creates a pressure gradient such that there is higher air pressure nearer the entrance and lower air pressure nearer the exit. This pressure gradient causes the ping pong ball to roll through the maze to exit. This is a brilliant application of a novel idea BUT the physical process at work only seems miraculous because we do not deal with acid gradients every day. Consider: would the same claims that it "performs a computation" be as credible in the vacuum cleaner and air pressure version? If any computation is being done, it is a search space being covered in parallel by billions of independent agents (the molecules of the medium). The movement of the water droplet (or ping pong ball!) merely serves to display the answer.