Optical Solution For an NP-Complete Problem?

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 N^N 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."

Comments

Not the first time this has been proposed

[jfengel]

This solves a nondeterministic-polynomial algorithm by using a very large number of parallel computations to simulate nondeterminism.

This was proposed some years ago for DNA computers as well, until somebody figured out that it would take a mass of DNA the size of the earth to figure out a non-trivial problem. So this is NOT the first time somebody has proposed a method for reducing NP problems to polynomial time, though this mechanism is novel as far as I know.

Photons are a lot smaller than DNA. N^N photons seems much more feasible. But even so... once N=100, 100^100 photons is way more than we can handle.

Re:Not the first time this has been proposed

[PhysicsPhil]

This solves a nondeterministic-polynomial algorithm by using a very large number of parallel computations to simulate nondeterminism.

This was proposed some years ago for DNA computers as well, until somebody figured out that it would take a mass of DNA the size of the earth to figure out a non-trivial problem. So this is NOT the first time somebody has proposed a method for reducing NP problems to polynomial time, though this mechanism is novel as far as I know.

I'm not sure this comparison is correct. The use of DNA just increased the computational power available to the problem, but didn't change the fundamental methods of calculation (i.e. one step at a time). The DNA computer didn't make the NP problem go away, it just threw more power at it.

This uses the interference of the light within an optical network to perform the calculation. The "operation", such as it is, relates to physically constructing the network rather than the number of photons required. In a very tenuous way, this is similar to a quantum computer, where multiple calculations are performed simultaneously. Of course it's not a quantum computer, but it does appear to be a polynomial algorithm.

Re:Not the first time this has been proposed

[SeanMon]

A CO2 laser at 500 kW generating a beam of 10 micrometer wavelength produces about about 2.52 x 10^25 photons per second. It will only take 1.25 x 10^167 years to generate 100^100 photons.
Just a bit more than we can handle.

Re:A general summary of the article

[Bender0x7D1]

One important part of any solution is the amount of time/cycles it takes to encode the problem for use in your algorithm.

For example, I can't claim that my algorithm can factor a number in O(1) if I require that the input for the algorithm is a vector of the prime factors for the desired number. Yes, my part of the algorithm is O(1), but to take a number and convert it to the format for my algorithm is not O(1), meaning the overall performance can't be considered O(1).

In summary, the time/cycles to set up the problem counts.