Oil Drop Navigates Complex Maze | Hacker News Reader

Oil Drop Navigates Complex Maze

sciencenow.sciencemag.org

23 pointsicey23 comments

This bears a striking resemblance to the HN posting on antiobjects: 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)

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

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.

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

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.

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.

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.

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.

Except that O(|V|^2 log|V|) is still polynomial.

(|V| > log|V|), therefore (|V|^2 |V| == |V|^3) > (|V|^2 log |V|). As a polynomial is a (loose) upper-bound, it cannot be greater than polynomial time, thus !NP-Complete.

Dijkstra's algorithm gives this as the worst-case performance (via http://en.wikipedia.org/wiki/Dijkstras_algorithm ), and finds shortest route from a root to all nodes, clearly including the exit:

  O( | E | + | V | log | V | )

Definitely not NP-Complete. Finding the distance from all nodes to all other nodes may be NP-Complete (not sure, but it seems like it would be, and doing so would be meaningless in a maze), but maze-solving is relatively easy in computing terms. Heck, even if you don't know the maze it's not NP-Complete: simply walk the whole thing and then calculate the shortest path.

Granted, the quote only says mazes can fall into NP-Complete... but I really don't know what you'd have to do to do that, without clearly falling out of a "maze" problem and into a more general "graph" problem.

The distance from all nodes to all other nodes is the Floyd-Warshall's All Shortest Paths algorithm, and it's V^3.

Cool, thanks! I've got more reading to do now :)

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?

Shortest path from one point to another in a graph is polynomial. Shortest path to all nodes is NP complete.

No, all-pairs shortest path problem is in P as well.

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.

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.

1. Shortest Path is NP complete? 2. Who says this is in N time?

The acid gradient provides extra information, which changes the complexity of the problem.

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

Personally I see no reason to believe this isn't true of all physical processes that "solve" an NP-complete problem.

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.

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

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.

Reply on news.ycombinator.com