Slashdot Mirror
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 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 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.
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.
Reading code is like reading the dictionary - you have to read half of it before you can go back and understand it.
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.
"FDA staff reviewers expressed concern about the number of patients who were left out of the study because they died."
"N+X" is called "addition": additive increase. "N+N" is called multiplication (2N): geometric increase, as is "N*X". "N*N" is called exponential (NX). What is "NN" called? And is there a higher order of increase?
And what are all those kinds of operations called?
--
make install -not war
Badonkadonk Land Cruiser Tank?
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.