[ExI] Stross on alleged NP-complete solution

[Damien Broderick]

This from Charlie Stross's blog:


August 7, 2007




Anyone know if this is for real?

<http://www.opticsexpress.org/abstract.cfm?id=140598>An 
Optical Solution For The Traveling Salesman Problem

They're claiming an O(NN) solution to a problem 
that is NP-complete. According to the abstract:
We introduce an optical method based on white 
light interferometry in order to solve the 
well-known NP–complete traveling salesman 
problem. To our knowledge it is the first time 
that a method for the reduction of non–polynomial 
time to quadratic time has been proposed. We will 
show that this achievement is limited by the 
number of available photons for solving the 
problem. It will turn out that this number of 
photons is proportional to NN for a traveling 
salesman problem with N cities and that for large 
numbers of cities the method in practice 
therefore is limited by the signal–to–noise 
ratio. The proposed method is meant purely as a gedankenexperiment.

This is either wrong, or (as Ken MacLeod put it) 
"we're all doomed". Anyone want to give it a 
read-through and tell me if it's plausible but 
impractical, implausible, or plausible and 
probably capable of being implemented?

[here are lots of comments:

<http://www.antipope.org/charlie/blog-static/2007/08/anyone_know_if_this_is_for_rea.html#comments> 
]