3 ms·

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

by 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.

by 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.