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)
I for one (Score:0, 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?)
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?
First Thoughts (Score:5, Funny)
Gasundheit!
GRB explanation (Score:4, Funny)
to which Charles Stross replies "Ah, so that's what the short duration GRBs are!"
Fnord.
Re:Some Reference info (Score:5, Funny)
Re:Better solution... (Score:3, Funny)
You've exceeded Slashdot's DMR (Score:4, Funny)
Re:So (a real comment)... (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.
P= NP (Score:3, Funny)
The researchers are just using an expoential number of photons to aid in the processing.
Josie Bauer addressed Travelling Salesman problem (Score:4, Funny)
Solution involved a Farmer's daughter, which she apparently was.
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?
Mad moderation. (Score:3, Funny)
Please, mods use some sense in moderating.
Re:Not the first time this has been proposed (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: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.
Re:Parallel computing (Score:5, Funny)
He may have said it, but he wasn't certain about it.
Re:Better solution... (Score:3, Funny)
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'.
Congratulations (Score:1, Funny)
...Although I suspect there may be a slightly faster algorithm.
Re:Parallel computing (Score:3, Funny)