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."
Some Reference info (Score:5, Informative)
The Travelling Salesman Problem [wikipedia.org]
and this doozy of a word : gedankenexperiment [wikipedia.org]
Re:First Thoughts (Score:5, Informative)
Yes, I believe it should have been Gedankeneksperiment [leo.org], with a capital G.
Freundliche Grüße,
Your friendly neighbourbood grammar Nazi
A general summary of the article (Score:5, Informative)
The experimenters are constructing the map of the various cities using optical fibres. Each city represents a junction in the optical fibre network, and each fibre has a length proportional to the weight of the edge joining two cities in the abstract problem.
Once the fibre network is constructed, they shine a white light source into the network. As the light propagates through the system, it splits at each junction (i.e. city). As a consequence, the optical signal is able to sample all possible paths through the network simultaneously. The entire optical network is put on one arm of an interferometer, and the length of the other arm (the reference arm) is adjusted. Starting from a known lower bound on the city length, the length of the reference arm is increased until the reference signal interferes with the output signal from the optical network. At that point, they have the length of the shortest path, and apparently can do some kind of reconstruction to get the actual path from there (didn't quite follow how that happened).
The claimed reduction of an NP problem to quadratic comes from the setup of the experimental apparatus. An "operation" consists of connecting one of the N cities to another of the N cities. For an average collection of cities, there will be a number of roads/connections proportional to N^2. Of course the operation is awfully slow, but it's a thought experiment more than anything.
NP != "Non-polynomial" (Score:5, Informative)
Re:Parallel computing (Score:5, Informative)
Re:NP != "Non-polynomial" (Score:5, Informative)
Re:NP != "Non-polynomial" (Score:5, Informative)
IMO, the only way to reduce NP-Complete problems is using something like quantum entanglement or another similar characteristic that is not bounded by classical physics.
My quack-o-meter is beeping (Score:5, Informative)
Also, "NP" doesn't stand for "non-polynomial". There is no such thing as "non-polynomial time". It's Nondeterministic Polynomial time.
These guys may know their optics, but they're amateurs in complexity theory. This is most painfully obvious in their concluding sentence:
Re:Some Reference info (Score:3, Informative)
Re:My quack-o-meter is beeping (Score:2, Informative)
Re:Parent post is not correct. (Score:3, Informative)
And yet, P and NP are defined in terms of a Turing machine. Herein lies the GPs point: it is taken as a given that the Turing machine is capable of computing any effectively computable function, but it is an open question as to whether we can build a different kind of machine which would be able to solve NP problems in polynomial time. By definition, the non-deterministic Turing machine solves NP problems in polynomial time, but we don't currently know how to build one.
Quantum computers may or may not be such a machine - we're really not sure yet (possible proofs have been advanced for both answers; the prevailing opinion is that none of them are likely to be correct and quantum computers are something entirely new that we don't understand). Other methods of computation also may exist. Our understanding of the fundamental laws of physics is grossly incomplete, so we can't tell. However, it seems unlikely that the computational capacity of the universe is adequately modelled by a Turing machine.
This relates to the question of "P=NP?" as follows: if such a machine can be built, then *some* machines can solve these problems in polynomial time. If P=NP, then *all* machines can solve these problems in polynomial time.
Re:NP != "Non-polynomial" (Score:1, Informative)
Re:So (a real comment)... (Score:3, Informative)
Re:NP != "Non-polynomial" (Score:3, Informative)
Whoah, whoah. Shor's Algorithm solves the factoring problem, which is almost certainly NOT NP-complete. (If it were, then NP would equal coNP, which would be almost as surprising as if NP equalled P.)