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.
We do not apriori know that the laws of physics cannot be (ab)used to cause a computation to happen in a way which is strictly better than the way a Turing machine (read 'pretty much any computer you can think of') works. Though this apparatus requires a large number of photons it is an exciting result towards what could be a real paradigm shift in computing. For similar reasons quantum computing is interesting to us, but it too has its drawbacks. Alternatively one could hope for an (IMHO unlikely) proof of P=NP, which would say that a Turing maching can after all achieve similar efficiency.
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
They claim n^2 time complexity. Then they point out the number of photons needed is n^n. There are physical limits to photon production rates. 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. It's an interesting method, but it doesn't actually improve the time complexity of the problem as they claim.
It's an analog computer solution to the problem; note that analog computers are not subject to limits based on theorems relating to Turing machines (and related algorithmic computational devices). However, the resources required still scale exponentially; the computation (if you want to call it that) is done by photons, and the number of photons required scales as N^N. Essentially, they are trading time for computational resources, where in this case the computational resource is "photons".
http://www.geoffreylandis.com
P is equal to NP because processing speed is increasing expoentially. Each year, the amount of processing you can do doubles.
The researchers are just using an expoential number of photons to aid in the processing.
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
"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
opticsexpress.com
I guess they were going for "optics express"
I of course read it as "optic sex press"
and there's no way you're getting me to click that link at work!
The parent post is woefully incorrect (just read a wikipedia article on NP completeness). But it is not a troll.
Please, mods use some sense in moderating.
SJW n. One who posts facts.
Actually, the running time is not reduced by the algorithm disclosed in the article. The disclosed algorithm has running time at least $O(2^N)$. The algorithm uses photons as parallel processors, but the shortest running time for any of those photons is $O(2^N)$. This is because the algorithm uses a time delay in the apparatus representing city $I$ equal to $\alpha 2^I$, where $\alpha$ is strictly longer than the longest city-to-city delay in the problem. In city $N$, the time delay is $\alpha 2^N$. The algorithm uses these time delays to differentiate between valid solutions and erroneous solutions to the TSP problem. For every valid solution, the photon representing that solution must pass through each city $i$, and must incur the corresponding delay. Hence, every valid solution is found only after time at least $\sum_{i=1}^N \alpha 2^i)$ or $O(2^N)$.
The article approaches a problem that Optics Express readers might not normally consider. And, it may represent a new application of optics technology (that is out of my field). But, the use of physical models to approach $NP$ problems is not new. And, the algorithm is not faster than other known algorithms for the same problem.
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
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.
In their setup, each city has a delay line (i.e. optical fibre.) Each new city you add has to have a delay line twice as long as the previous one you added. The required amount of fibre grows exponentially with the number of cities.
Quattuor res in hoc mundo sanctae sunt: libri, liberi, libertas et liberalitas.