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."
Not the first time this has been proposed (Score:5, Interesting)
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 (Score:5, Interesting)
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:A general summary of the article (Score:5, Interesting)
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.
Re:Some Reference info (Score:3, Interesting)
While this is just a thought experiment, I think their use of interferometry to solve problems is pretty interesting, since it really is in some respects quantum computing. While, as they note, it isn't a quantum computer in the usual sense with entanglement and qubits, their method does, after all, depend on light following Fermat's Principle of Least Time, which in turn can be considered a consequence of quantum electrodynamics. It makes me wonder what other sorts of computational problems can be solved using invariant properties of the physical world.
Increasing Orders (Score:2, Interesting)
And what are all those kinds of operations called?
Re:Not the first time this has been proposed (Score:5, Interesting)
Just a bit more than we can handle.
Re:Some Reference info (Score:2, Interesting)
Re:NP != "Non-polynomial" (Score:3, Interesting)
Photons are not bounded by classical physics, and their behaviour can only be explained by quantum physics. Whether or not this behaviour can be exploited to perform computation more efficiently than a Turing machine is unknown (and will likely remain that way until we untangle the problem of how quantum physics really works). We still do not have a complete understanding of how they behave, and much of what we think we know is unproven. This idea's pretty far out on the edge of plausibility, but even if this particular method turns out to be flawed, we don't know enough to be sure that no other similar methods could work. (We also don't know whether quantum computing can do it, which is one of the big open questions in that field)
That statement is true only under the assumption that the model of computation is a form of Turing machine. The essential property of a Turing machine is that they can compute any effectively computable function. There is no particular reason to believe that they also have the property of describing the limits of what the physical universe can compute in a given space of time, and in fact they don't for some simple problems, although we haven't found any machines that can tackle NP problems yet. Even under "classical" physics, we're uncertain whether such a machine could exist; nothing in classical physics says that they can't, so far as we know.
This question is right up there alongside "P=NP?", and has similar properties: we suspect and usually assume that such machines don't exist, but don't have anything resembling a good reason to believe this, other than "we haven't found one yet". It's not as interesting as "P=NP?" because in most cases, there is no way to prove something to be physically impossible (since you can never be sure that you have found the most fundamental laws of physics), so the question may remain unresolved forever.