Optical Solution For an NP-Complete Problem? 232
6 writes to let us know that two optical researchers have proposed, as a thought experiment, a novel idea for solving the traveling salesman problem. From 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."
Parallel computing (Score:5, Insightful)
Re:Some Reference info (Score:1, Insightful)
Turing Machine vs Laws of Physics (Score:2, Insightful)
Re:Parallel computing (Score:5, Insightful)
Still an exponential algorithm (Score:4, Insightful)
N*d + a*(2^N+1)
Since the speed of light is finite, the algorithm still takes O(2^N) i.e. exponential time to complete.
exponential photons == not practical (Score:5, Insightful)
Re:Some Reference info (Score:2, Insightful)
Re:Not the first time this has been proposed (Score:4, Insightful)
Translation, "We know this wont ever work; we just think it's cool."
Even better is in section five where they cite Wikipedia for the definition of a quantum computer.
The run time is wrong (Score:3, Insightful)
Exponential in computational resources (Score:2, Insightful)
Re:exponential photons == not practical (Score:2, Insightful)
Guess you missed this part.
Poor choice of domain name (Score:2, Insightful)
I guess they were going for "optics express"
I of course read it as "optic sex press"
and there's no way you're getting me to click that link at work!
The given algorithm is $O(2^N)$ (Score:3, Insightful)
Actually, the running time is not reduced by the algorithm disclosed in the article. The disclosed algorithm has running time at least $O(2^N)$. The algorithm uses photons as parallel processors, but the shortest running time for any of those photons is $O(2^N)$. This is because the algorithm uses a time delay in the apparatus representing city $I$ equal to $\alpha 2^I$, where $\alpha$ is strictly longer than the longest city-to-city delay in the problem. In city $N$, the time delay is $\alpha 2^N$. The algorithm uses these time delays to differentiate between valid solutions and erroneous solutions to the TSP problem. For every valid solution, the photon representing that solution must pass through each city $i$, and must incur the corresponding delay. Hence, every valid solution is found only after time at least $\sum_{i=1}^N \alpha 2^i)$ or $O(2^N)$.
The article approaches a problem that Optics Express readers might not normally consider. And, it may represent a new application of optics technology (that is out of my field). But, the use of physical models to approach $NP$ problems is not new. And, the algorithm is not faster than other known algorithms for the same problem.
Re:Parallel computing (Score:3, Insightful)
However, it uses exponential resources (Score:3, Insightful)