Slashdot Mirror

← Back to Stories (view on slashdot.org)

Let Nature Solves NP-Complete Problem

Posted by timothy on from the unconventional-approaches dept.

An Anonymous Coward writes: "Why not? Here's a start: Tourist Map Illuminates shortest route Light up a gas-tube graph with electricity to find the shortest path between two points. Can they extend this to multiple vertices to instantly solve the NP-Complete traveling salesman problem?"

3 of 48 comments (clear)

  1. I prefer the slime mould version... by SIGFPE · · Score: 4, Informative

    ...here

    --
    -- SIGFPE
  2. Shortest-path problems are easy ... by Daniel+Dvorkin · · Score: 4, Informative

    ... for computers too. Any decent book on algorithms will give you several elegant, easy-to-implement, blazingly fast methods. The TSP, like all NP problems, is much different. Thinking about the gas-tube device (which is a really cool idea, I must say) there's no way to apply it to the TSP. Electricity just doesn't work that way.

    --
    The correlation between ignorance of statistics and using "correlation is not causation" as an argument is close to 1.
  3. Re:Question by Fantanicity · · Score: 3, Informative

    The current doesn't oscillate or travel solely along the path of least resistance.
    Electrons do not select anything. The current flows from start to finish along all possible paths; but because the shortest path has the least resistance (there is less material to flow through) more electrons get through that path per unit time than other paths - hence the current is higher.
    In this case, all paths will glow, the shortest path will glow the most. With the right balance of voltage and material, the shortest path can glow significantly more than other paths.