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

1 of 48 comments (clear)

  1. Re:shortest path IS np-complete NOT by gkatsi · · Score: 5, Insightful

    First, shortest path algorithms do NOT consider every possible route. Instead, they consider the best extention to an already known shortest path (starting with the shortest path to the beginning, which is obviously 0). [roughly -- Dijsktra's algorithm is slightly more complicated, but not much].

    Second, if the number of operations increases polynomially, how does the problem get classified as NP complete? Never mind the fact that a lower bound alone is not enough to put a problem in a specific class, if the complexity is actually O(n^2), then the problem is clearly in P, not NP.

    Other than a nice hack, this article does not describe any important breakthrough.