Let Nature Solves NP-Complete Problem

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

Comments

This would be excellent news ...

[Anonymous Coward]

... if finding the shortest route between 2 points on a network was actually an NP-Complete problem

Re:shortest path IS np-complete NOT

[gkatsi]

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.

Re:Neat, but not quite as useful as one might thin

[Anonymous Coward]

Furthermore it doesn't solve the problem satisfactorily, for instance how do you make a one way street in a neon tube?

Diodes (allows current to flow only one way)

How do you post speed limits for electrons?

Resistors (regulates the flow of current more than the speed -- but you get the idea)

TSP means Travelling salesman problem

[invictus]

I am being stupid and talking out of my ass, the original post was about the Travelling salesman problem, which is npc... and I misread your post as being about the main post being non-npc -- i.e. this whole conversation was line noise. my bad.

let's reiterate - traveling salesman: np-complete

shortest path between two arbitrary points in a graph of n points - O(n^2)

/me should go get some more caffeine