Hacker News Reader

Comment by bioweek | Hacker News Reader

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?

View on HN

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.

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

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.

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.

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

Reply on news.ycombinator.com