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?"

5 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:shortest path IS np-complete NOT by invictus · · Score: 2, Informative

    it's called leinthal's paradox -- the cost is NOT O(n^2) the cost is O((n-1)!) (http://konf2.ims.ac.jp/review/sec4.html)
    Djikstr a's algorithm merely simplifies the correct procedural solution by limiting the sample space (which introduces a possibility of error) -- it APPROXIMATES the solution because the exact calculation is NP-Complete... another reference: here

    --
    --Ks9
  4. Answering the question by andfarm · · Score: 2, Informative

    No.

    This resistance-path method will only find the shortest path from one point to another -- a task for which there already exist solutions which can complete in polynomial time. A *full* path (which is required as a solution to the Travelling Salesman problem) is not directly solved by this method.

    --

    TANSTAAFI: There Ain't No Such Thing As A Free iPod.

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