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.
I for one am welcomming our new briefcase carrying shiny shoes foot in the door encylopadea selling in most efficient manners overloads!
Will code for new sig.
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, 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
...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.
Badonkadonkexperiment ???
Launch every sig.
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
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.
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
So, are you saying that this is a pretty bright idea? Or that it's not so bright?
See what I've been reading.
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.
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.
>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.
...and Heisenberg says you never will.
He may have said it, but he wasn't certain about it.
When our name is on the back of your car, we're behind you all the way!
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
...Although I suspect there may be a slightly faster algorithm.
Schrödinger's cat wasn't going to commit to one side or the other until he saw it in action.
When our name is on the back of your car, we're behind you all the way!