3 ms·

Very interesting. I don't think slime-molds are fast enough to build a useful NP-oracle, though.

• pmiller2 14y ago
  MST is polynomial, so you can't use it as an NP oracle, anyway.
  • hythloday 14y ago
    And the fact that the slime molds didn't create the same layout every time implies they don't provide an optimum answer.
    • ganley 14y ago
      Not necessarily true. There could be multiple, equal-valued optima.
      • pmiller2 14y ago
        Exactly. Consider the case of all equal weights. In that case, every spanning tree is a MST. For the extreme cases (labeled complete graph, and a tree) of order n, those numbers are $n^{n-2}$ and 1, respectively, so the answer can be far from unique.