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."
Better solution... (Score:5, Funny)
Re: (Score:3, Funny)
Re: (Score:3, Funny)
Article is also NP-Complete Problem (Score:4, Funny)
Obligatory (Score:5, Funny)
(Did I mention how much I hated my Computability and Complexity courses when I was in college?)
Parallel computing (Score:5, Insightful)
Re:Parallel computing (Score:5, Insightful)
Re:Parallel computing (Score:5, Informative)
Re: (Score:3, Insightful)
I guess it depends what you mean by 'computation'. As the article itself says,
Unsurprisingly, they need an exponential amount of photons (and even N^N, whereas we know the problem is solvable u
Re: (Score:2)
Re:Parallel computing (Score:5, Funny)
He may have said it, but he wasn't certain about it.
Re: (Score:2)
Re: (Score:2)
It was Schrödinger's cat that would really know, not Heisenberg's.
Re: (Score:3, Funny)
Some Reference info (Score:5, Informative)
The Travelling Salesman Problem [wikipedia.org]
and this doozy of a word : gedankenexperiment [wikipedia.org]
Re:Some Reference info (Score:5, Funny)
Re: (Score:2, Interesting)
Re: (Score:2)
Re: (Score:2)
Re: (Score:2, Insightful)
Re: (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, t
Re: (Score:2)
Re: (Score:3, Informative)
So (a real comment)... (Score:5, Funny)
What is the optimum path the fibre fitter must take to lay all the cables and reduce his mileage?
Re: (Score:3, Informative)
Re: (Score:2, Funny)
The travelling fibre layer must visit every city from every other city making his journey MUCH longer than the original salesman.
Might be easier just giving the fibre fitter a second moonlighting job as a salesman.
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.
But Requires Exponential Photons... (Score:2)
It'd be a little like having an polynomial time algorithm that required exponential space. Interesting oddity, but unfortunately not useful in itself.
Re:Not the first time this has been proposed (Score:4, Insightful)
Translation, "We know this wont ever work; we just think it's cool."
Even better is in section five where they cite Wikipedia for the definition of a quantum computer.
Re:Not the first time this has been proposed (Score:5, Interesting)
Just a bit more than we can handle.
Re: (Score:2, Funny)
Or to put it a little more excitingly, solving a 26 step problem with 12um photons will take somewhere in the region of 25 megatons.
Which means you would probably have to be pretty desperate for sales.
Re: (Score:2)
Still, they say that for larger problem sets the SNR makes detection and filtering too difficult. Larger problem sets are precisely where one worries the most about computational complexity, of course. So it's still, at least for now, just a neat trick.
Re: (Score:2)
That's still a lot, but it's far fewer than n**n.
Still, it does seem that it limits it to the "neat trick" category.
Re: (Score:2)
To be NP, it means that it can be solved by a nondeterministic machine in polynomial time. Or, to put it another way, if you already knew the answer, you could check that it was the correct one in polynomial time.
It's not just "non-polynomial". There are plenty of problems that are truly non-polynomial: they'd be exponential to verify even if you already knew the correct answer. Whether a Turing machine will terminate on a given input is EXPTIME, and can
Re: (Score:2)
Re: (Score:2)
First Thoughts (Score:5, Funny)
Gasundheit!
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
More precisely, wouldn't you be a German Nazi? (Score:4, Funny)
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'.
GRB explanation (Score:4, Funny)
to which Charles Stross replies "Ah, so that's what the short duration GRBs are!"
Fnord.
You've exceeded Slashdot's DMR (Score:4, Funny)
Re: (Score:2)
Re: (Score:2)
Re: (Score:2)
I had to look up who the heck Charles Stross is. He sounds like my kind of author
Here's [accelerando.org] one of his books if you'd like to check.
are all good sci-fi authors from the UK these days?
No. Peter Watts [rifters.com] is Canadian. You can check [rifters.com] to see if he's decent too (people are going nuts over Blindsight atm).
Greg Egan [netspace.net.au] is Australian, and there's plenty of supporting information of his existing work and a few of his short stories on there if you're not familiar with him.
Gedankenexperiment ? (Score:2)
Re: (Score:2)
Re: (Score:2)
No, it's watching at die Blinkenlichten, silly!
Uhm. I wonder how many people outside Slashdot would understand this exchange
Turing Machine vs Laws of Physics (Score:2, Insightful)
Parent post is not correct. (Score:2)
Re: (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 so
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.
The run time is wrong (Score:3, Insightful)
Re:The run time is wrong (Score:4, Funny)
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.
Exponential in computational resources (Score:2, Insightful)
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: (Score:2)
NP != "Non-polynomial" (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.
Re: (Score:2)
Crank or no?
Re: (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.)
Re: (Score:2)
I came up with the string solution.
You cut pieces of string equal to the distance between the cities, and tie each piece of string to two rings representing the cities, and label each ring with a city's name. To solve the problem for any pair of cities, you pick up the ri
Re: (Score:2)
That doesn't solve the TSP -- it solves the shortest path problem. The TSP requires the salesman to visit every city; your method will only visit a subset of the cities. As a simple thought experiment, consider that the string method cannot give a path that starts and ends in the same city. The shortest path problem is already solvable in O(N^2), as a classic tree/graph searching problem.
Re: (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 no
Re: (Score:2)
"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"
- Which light fits nicely.. so what's your problem?
The problem is that using such a technology or technique does not change the complexity of the problem. NP-complete is still NP-complete, and P still != NP. NP-complete refers to that set of problems whose best solutions can only be solved in nondeterministic polynomial time. That means that using a standard CPU running one or any fixed constant number of operations per clock tick, the time needed to find a solution increases very quickly. The solution in TFA essentially creates an approximation of a nonde
Still an exponential algorithm (Score:4, Insightful)
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.
Re: (Score:2)
Since the speed of light is finite, the algorithm still takes O(2^N) i.e. exponential time to complete.
Yes, but at least in theory the paths can be made almost infinitely short. At some point the energy density of the photons will overwhelm spacetime and form a black hole, however :-)
exponential photons == not practical (Score:5, Insightful)
Re: (Score:2, Insightful)
Guess you missed this part.
Re:exponential photons == not practical (Score:5, Funny)
So, are you saying that this is a pretty bright idea? Or that it's not so bright?
Re: (Score:2)
P= NP (Score:3, Funny)
The researchers are just using an expoential number of photons to aid in the processing.
Mad moderation. (Score:3, Funny)
Please, mods use some sense in moderating.
Re: (Score:2)
And it is true that if you have expoentially increasing computational resources you can solve NP problems in polynomial time.
Re: (Score:2)
That would be true, but we don't have exponentially increasing computational resources. Moore's Law, for instance, describes geometric increase.
Poor server... (Score:2)
Reminds me of rainbow sort (Score:2)
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: (Score:2)
Non-polynomial wouldn't mean the same thing as NP... You could put together an algorithm that is non-polynomial on a non-deterministic computer, too, which would be non-polynomial and not NP. It would be harder than NP.
Re: (Score:2, Informative)
I agree with everything you have to say, with one nitpicking exception: non-polynomial time seems a reasonable term to use. An algorithm that is O(N^N) takes time that is not polynomial in N, hence it is non-polynomial time.
I disagree. They're not talking about an algorithm here; they're talking about the Traveling Salesman Problem. They called the TSP "non-polynomial", and that is by no means certain. If you could prove that the TSP has no polynomial-time solution, you'd get the Turing award.
Re: (Score:2)
Josie Bauer addressed Travelling Salesman problem (Score:4, Funny)
Solution involved a Farmer's daughter, which she apparently was.
Increasing Orders (Score:2, Interesting)
And what are all those kinds of operations called?
Re: (Score:2)
Re: (Score:2)
Re: (Score:2)
http://en.wikipedia.org/wiki/Tetration [wikipedia.org]
Re: (Score:2)
Is there a higher order of increase? And what are all those kinds of operations called?
Yes, there are plenty of functions which grow faster than an exponential. Some of the most well known (and easier to understand) include the Knuth up-arrow [wikipedia.org], the hyper operator [wikipedia.org], the Conway chained arrow [wikipedia.org]...
What's interesting to note is that some of those functions like the busy beaver [wikipedia.org] (!), although well defined and somewhat simple, cannot even be computed. We only know that they are BIG !
Re: (Score:2)
2^4 = 16; 2^^4 = 2^(2^(2^2)) = 2^(2^4) = 2^16 = 65536 (2^^n is ackermann(4, n+3)-3 )
2^^^4 = 2^^(2^^(2^^2)) = 2^^(2^^(4)) = 2^^6
Poor choice of domain name (Score:2, Insightful)
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!
Re: (Score:2)
But once I get home...
In other news... (Score:2)
I would note, however, that a more useful result does exist: many O(n log n) problems reduce to O(n) given the availability of log n processors. As log n is generally small this requires only a trivial application of parallelism. Merge sort, one of the staples of database engines, is a good example.
Analog reference (Score:2)
The given algorithm is $O(2^N)$ (Score:3, Insightful)
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.
glass map of london (Score:2)
http://www.rsc.org/publishing/journals/LC/article
Definition of gedankenexperiment (Score:2)
Sounds ridiculous (Score:2)
Also I don't see (from the abstract) how they're going to extract the desired shortest answer from all the wrong answers and reflections.
First time (Score:2)
Let n = number of cities.
1. Cut strings to length of path between cities: O(n^2))
2. Tie together ends of links that meet at same city: O(n^2))
3. Grab start and destination endpoints in each hand, and pull taut: O(1)
4. Mark route along links that have tension in them: O(n)
Overall complexity: O(n^2)
However, it uses exponential resources (Score:3, Insightful)
Re: (Score:2)