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 N^N 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."

Comments

Better solution...

[Anonymous Coward]

I think a couple of gaurd dogs and a shotgun are a good enough method to solve the travelling salesman problem.

Article is also NP-Complete Problem

[LiquidCoooled]

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.

Obligatory

[Tackhead]

"Nothing to see here. Please move along, but no, no, no, not over that bridge, you idiot! That's another one of those fucking pathological edge cases that invalidates what would have been an otherwise great TSP equivalence proof, and now I have to start all over again! Curse you, Konigsberg, why didn't the Brits and the Russians and the Germans finish you off when you were fair game!"

(Did I mention how much I hated my Computability and Complexity courses when I was in college?)

So (a real comment)...

[LiquidCoooled]

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?

First Thoughts

[TheRequiem13]

...gedankenexperiment...
Gasundheit!

GRB explanation

[a.d.venturer]

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.

Re:Some Reference info

[ZOMFF]

Badonkadonkexperiment ???

Re:exponential photons == not practical

[RealAlaskan]

... 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.

So, are you saying that this is a pretty bright idea? Or that it's not so bright?

Re:Parallel computing

[camperdave]

...and Heisenberg says you never will.

He may have said it, but he wasn't certain about it.