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

Better solution...

[by Anonymous Coward]

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

Re:

[spun (1352)]

You don't even need to go that far. In fact, if you don't have an attractive teenage daughter you should be all right. If you do, you simply do not let the traveling salesman sleep anywhere on your property. Or so I've heard.

Re:

[AndersOSU (873247)]

If you have a hot daughter odds are you already had a traveling salesman problem, you just didn't know about it.

Article is also NP-Complete Problem

[LiquidCoooled (634315)]

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 (54550)]

"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 (583406)]

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 (814657)]

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 (1087643)]

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:

[kripkenstein (913150)]

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.

I guess it depends what you mean by 'computation'. As the article itself says,

So in total we will need [about] (5/64)*N^N photons.

Unsurprisingly, they need an exponential amount of photons (and even N^N, whereas we know the problem is solvable u

Re:Parallel computing

[camperdave (969942)]

...and Heisenberg says you never will.

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

Re:

[camperdave (969942)]

Schrödinger's cat wasn't going to commit to one side or the other until he saw it in action.

Some Reference info

[Fox_1 (128616)]

Heh, to give you a better idea of what the abstract is talking about:
The Travelling Salesman Problem [wikipedia.org]
and this doozy of a word : gedankenexperiment [wikipedia.org]

Re:Some Reference info

[ZOMFF (1011277)]

Badonkadonkexperiment [wikipedia.org] ???

Re:

[morgan_greywolf (835522)]

Well, even if you knew what the TSP is, it might be, depending on your chosen profession, that you may not recall of the specifics regarding the TSP, such as the formulae used, what sorts of algorithms may be used to solve the problem, etc. Not all of us have jobs where we use our math/computational science/computer science skills on a day-to-day basis.

Re:

[reverseengineer (580922)]

On the subject of Wikipedia, the authors of this paper actually use Wikipedia on page 9 of their paper to provide a definition of a quantum computer. (They don't bother with a full citation like they use for their other sources though.)

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:

[faragon (789704)]

Babbage was mechanical, while the proposed in the article seems more like a classic analog computer [wikipedia.org] but using photons instead electrons.

So (a real comment)...

[LiquidCoooled (634315)]

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?

Re:

[evanbd (210358)]

So, on a serious note, the fiber installer (who has to traverse each edge) is different from the salesman (who has to visit each node). The problem of the installer is the Chinese Postman Problem [wikipedia.org], and is actually *not* NP-complete. In fact, the current best approximate solutions to the TSP involve transforming it to the CPP, solving that, and then transforming it back. (Sorry, I'm not clear on the details.)

Not the first time this has been proposed

[jfengel (409917)]

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 (880677)]

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 (944892)]

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 (929653)]

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 (978749)]

...gedankenexperiment...

Gasundheit!

Re:First Thoughts

[codeButcher (223668)]

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?

[JimTheta (115513)]

Your friendly neighbourbood grammar Nazi

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

[a.d.venturer (107354)]

As pointed out here [antipope.org] "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.

You've exceeded Slashdot's DMR

[spun (1352)]

That joke has too high of a Dennis Miller ratio [snpp.com] even for Slashdot.

Gedankenexperiment ?

[OpenSourced (323149)]

Is that something like watching at the blinkenlights?

Turing Machine vs Laws of Physics

[TheEmptySet (1060334)]

We do not apriori know that the laws of physics cannot be (ab)used to cause a computation to happen in a way which is strictly better than the way a Turing machine (read 'pretty much any computer you can think of') works. Though this apparatus requires a large number of photons it is an exciting result towards what could be a real paradigm shift in computing. For similar reasons quantum computing is interesting to us, but it too has its drawbacks. Alternatively one could hope for an (IMHO unlikely) proof of

Re:

[asuffield (111848)]

You are confused about the definition of a Turing machine. A Turing machine says nothing about computational efficiency.

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

[PhysicsPhil (880677)]

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.

The run time is wrong

[gr8_phk (621180)]

They claim n^2 time complexity. Then they point out the number of photons needed is n^n. There are physical limits to photon production rates. 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. It's an interesting method, but it doesn't actually improve the time complexity of the problem as they claim.

Re:The run time is wrong

[SamP2 (1097897)]

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

Exponential in computational resources

[Geoffrey.landis (926948)]

It's an analog computer solution to the problem; note that analog computers are not subject to limits based on theorems relating to Turing machines (and related algorithmic computational devices). However, the resources required still scale exponentially; the computation (if you want to call it that) is done by photons, and the number of photons required scales as N^N. Essentially, they are trading time for computational resources, where in this case the computational resource is "photons".

Re:A general summary of the article

[Bender0x7D1 (536254)]

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 (1008081)]

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 (170430)]

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 (199509)]

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.

Re:

[asuffield (111848)]

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.

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:

[cpeikert (9457)]

Shor's Algorithm, which solves an NP-whatever problem in (log n)^3 time, works because it draws computational power from another universe.

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

Still an exponential algorithm

[n01 (693310)]

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 (91710)]

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 (576404)]

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

P= NP

[naoursla (99850)]

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.

Mad moderation.

[serviscope_minor (664417)]

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.

My quack-o-meter is beeping

[p3d0 (42270)]

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.

Josie Bauer addressed Travelling Salesman problem

[karlandtanya (601084)]

Some time ago.

Solution involved a Farmer's daughter, which she apparently was.

The given algorithm is $O(2^N)$

[natoochtoniket (763630)]

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.

However, it uses exponential resources

[Michael Woodhams (112247)]

In their setup, each city has a delay line (i.e. optical fibre.) Each new city you add has to have a delay line twice as long as the previous one you added. The required amount of fibre grows exponentially with the number of cities.

Re:

[Yusaku Godai (546058)]

Nevermind, now it's working. I was getting server errors at first.