Aug 09 2007
The Eschaton is Immanent!
Hmm.. Looks like the Eschaton is imminent (and immanent) (An Optical Solution for the Traveling Salesman Problem)!
Anyway I was just reading a Charlie Stross short story with this same theme (e.g. researcher finds polynomial time solution to the NP-hard TSP problem, all hell breaks loose).
Apparently its a proposal that relies on the wave collapse / quantum properties of photons to build the mechanism (thus a kind of quantum computer). Photons take all possible paths in the mechanism, and observation collapses wave function in such a way to reveal shortest path.
Oops, looks like scaling up solution is still impossible, however, as power needs to scale exponentially to overcome signal-to-noise ratio, which, if I understand the article, makes use above 30 or so cities impractical. Oh well, guess we need to wait a few more years…