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?)

Parallel computing

[iamacat]

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

Re:Parallel computing

[bateleur]

The ironic thing being that this is precisely why we care about whether NP=P or not. Because without a polynomial time algorithm, large problems remain intractable even after you massively parallelize them!

Re:Parallel computing

[CaptainPatent]

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). No. While the language of the paper is indeed rather thick, it seems they are using interference to get individual photons of light to traverse every pathway simultaneously. Even if I am only partially correct there, the photons in the experiment are only detected and are never being used as an instrument for computation.

Re:Parallel computing

[camperdave]

...and Heisenberg says you never will.

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

Some Reference info

[Fox_1]

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

Re:Some Reference info

[ZOMFF]

Badonkadonkexperiment ???

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?

Not the first time this has been proposed

[jfengel]

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.

Re:Not the first time this has been proposed

[PhysicsPhil]

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.

Re:Not the first time this has been proposed

[mdmkolbe]

From the last line of the abstract, "The proposed method is meant purely as a gedankenexperiment."

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

[SeanMon]

A CO2 laser at 500 kW generating a beam of 10 micrometer wavelength produces about about 2.52 x 10^25 photons per second. It will only take 1.25 x 10^167 years to generate 100^100 photons.
Just a bit more than we can handle.

First Thoughts

[TheRequiem13]

...gedankenexperiment...
Gasundheit!

Re:First Thoughts

[codeButcher]

Yes, I believe it should have been Gedankeneksperiment, with a capital G.

Freundliche Grüße,

Your friendly neighbourbood grammar Nazi

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.

A general summary of the article

[PhysicsPhil]

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.

Re:A general summary of the article

[Bender0x7D1]

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.

NP != "Non-polynomial"

[imasu]

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.

Re:NP != "Non-polynomial"

[The Night Watchman]

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? That sounds right to me. I don't like how they're claiming that "the complexity of the traveling salesman problem can be dramatically reduced from N! to N^2 by optical means." They're not reducing the complexity of the problem at all. What they're doing is designing a parallel processing system that can approximate a nondeterministic Turing machine, thereby allowing the problem to be solved in polynomial time. This does nothing to indicate that P=NP. While they do make that point clear, I still take issue with their claim that they're doing anything at all to the complexity of the original problem.

Re:NP != "Non-polynomial"

[teknopurge]

Please mod parent and GP up. My thesis was on NP-Complete problems and combinatorial optimization and as soon as I saw "photons" I knew this was bunk. It does not matter what instrument you use: CPU core, Network Node, DNA, Molecule, Q-bit, electron-spin, etc. They are all constructs to illustrate problems. The entire point of NP-complete problems is that they cannot be solved and verified in reasonable time using anything that has a physical limitation: a clock speed, a limited number-of-sides, a finite number of nodes in a graph, finite degrees of spin, etc.

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.

Still an exponential algorithm

[n01]

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.

exponential photons == not practical

[frankie]

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.

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?

My quack-o-meter is beeping

[p3d0]

To our knowledge it is the first time that a method for the reduction of non-polynomial time to quadratic time has been proposed. This is far from the first time that someone has claimed to solve an NP-complete problem in P time by limiting the size of the problem. It's not that hard to design a circuit that solves TSP in polynomial time if you get to put a limit on the number of edges.

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.