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."
I think a couple of gaurd dogs and a shotgun are a good enough method to solve the travelling salesman problem.
In order that you can solve the article and produce feasible text in quadratic time you have to use a novel technique of installing a PDF reader.
liqbase
(Did I mention how much I hated my Computability and Complexity courses when I was in college?)
So effectively each photon is a CPU core and the running time is reduced by massive parallel computing rather than inherent reduction in complexity, which is (N^N)*(N^2).
Heh, to give you a better idea of what the abstract is talking about:
The Travelling Salesman Problem
and this doozy of a word : gedankenexperiment
The rock, the vulture, and the chain
So, to find out the shortest path for a travelling salesman you have to have a travelling Fibre fitter installing cables between all the cities?
What is the optimum path the fibre fitter must take to lay all the cables and reduce his mileage?
liqbase
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.
...gedankenexperiment...Gasundheit!
What?
As pointed out here "Apparently the method is polynomial in time, but exponential in energy ..."
to which Charles Stross replies "Ah, so that's what the short duration GRBs are!"
Fnord.
I browsed through the article, and here is my understanding of what they are doing.
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.
First off, NP does not mean "non-polynomial", it means "nondeterministically polynomial". Which means, the set of problems that can be solved in polynomial time on a nondeterministic turing machine. They are not reducing an NP problem to P here, which would require that their algorithm be executable on a deterministic turing machine in polynomial time. Rather, they are saying that if they effectively simulate a limited nondeterministic turing machine by increasing the number of compute units (in this case, photons) to effectively infinite numbers, then there is a polynomial solution. Which, since the travelling salesman problem is known to be in NP, is not surprising. Or am I misreading this? What IS cool is that they have found a way to actually effectively simulate a subset of a nondeterministic turing machine.
The paper says that the path the photons have to travel for a TSP with N cities is
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.
To solve a 50-point traveling salesman using their algorithm would require on the order of 50^50 photons (about 10^85). For comparison, the Sun emits roughly 10^45 photons per second. Somehow I don't think their system is going to scale very well.
That joke has too high of a Dennis Miller ratio even for Slashdot.
- None can love freedom heartily, but good men; the rest love not freedom, but license. -- John Milton
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: Since for practical (non-pathological) problems by purely electronic means very good solutions to even large size problems can be found, our proposed method is not meant to solve real-world traveling salesman problems but rather as a gedankenexperiment to show how photons and the laws of physics can considerably reduce the computational complexity of difficult mathematical problems. It does no such thing. All it does is parallelize the computation.
Patrick Doyle
I mod down every jackass who puts his moderation policy in his sig. Oh, wait a sec....
Solution involved a Farmer's daughter, which she apparently was.
"Reality is that which, when you stop believing in it, it doesn't go away." - Philip K. Dick
>I would say they're still looking at an n^n problem unless they can produce an infinite number of photons instantly, and that would damage the equipment
If you can produce an infinite number of photons instantly than I don't think you'd be worried about any kind of equipment.
For starters, try producing an infinite number of photons non-instantly (in a finite period of time), OR try to produce a finite number of photons instantly. Equipment will be the least of your problems.
If I had a hard-ass Spanish teacher correcting my Spanish, then I'd call him/her a "Spanish Nazi". So, you know, if you were correcting my German, it stands to follow...
I'm just sayin'.
My stupid web site