# Optical Solution For an NP-Complete Problem?

#### kdawson posted more than 6 years ago | from the too-bad-about-the-noise dept.

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 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... (5, Funny)

## Anonymous Coward | more than 6 years ago | (#20171931)

## Re:Better solution... (2, Funny)

## spun (1352) | more than 6 years ago | (#20172285)

## Re:Better solution... (0)

## Anonymous Coward | more than 6 years ago | (#20172293)

## I for one (2, Funny)

## Mipoti Gusundar (1028156) | more than 6 years ago | (#20171939)

## Article is also NP-Complete Problem (4, Funny)

## LiquidCoooled (634315) | more than 6 years ago | (#20171947)

## Obligatory (4, Funny)

## Tackhead (54550) | more than 6 years ago | (#20171973)

no, no, no, not overthatbridge, 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 (4, Insightful)

## iamacat (583406) | more than 6 years ago | (#20171991)

## Re:Parallel computing (4, Insightful)

## bateleur (814657) | more than 6 years ago | (#20172195)

whywe care about whether NP=P or not. Because without a polynomial timealgorithm, large problems remain intractable even after you massively parallelize them!## Re:Parallel computing (4, Informative)

## CaptainPatent (1087643) | more than 6 years ago | (#20172209)

## Re:Parallel computing (2, Insightful)

## kripkenstein (913150) | more than 6 years ago | (#20173481)

## Re:Parallel computing (1)

## 2short (466733) | more than 6 years ago | (#20172919)

## Re:Parallel computing (4, Funny)

## camperdave (969942) | more than 6 years ago | (#20173349)

...and Heisenberg says you never will.He may have said it, but he wasn't certain about it.

## Some Reference info (4, Informative)

## Fox_1 (128616) | more than 6 years ago | (#20172005)

The Travelling Salesman Problem [wikipedia.org]

and this doozy of a word : gedankenexperiment [wikipedia.org]

## Re:Some Reference info (1, Insightful)

## Anonymous Coward | more than 6 years ago | (#20172125)

## Re:Some Reference info (0)

## Anonymous Coward | more than 6 years ago | (#20172185)

## Re:Some Reference info (2, Interesting)

## reverseengineer (580922) | more than 6 years ago | (#20172621)

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, their method does, after all, depend on light following Fermat's Principle of Least Time, which in turn can be considered a consequence of quantum electrodynamics. It makes me wonder what other sorts of computational problems can be solved using invariant properties of the physical world.

## Re:Some Reference info (1)

## Fox_1 (128616) | more than 6 years ago | (#20172713)

## Re:Some Reference info (1)

## Yetihehe (971185) | more than 6 years ago | (#20172949)

## Re:Some Reference info (2, Informative)

## faragon (789704) | more than 6 years ago | (#20173177)

## Re:Some Reference info (1)

## Gr8Apes (679165) | more than 6 years ago | (#20173351)

## Re:Some Reference info (2, Insightful)

## morgan_greywolf (835522) | more than 6 years ago | (#20172277)

## Re:Some Reference info (5, Funny)

## ZOMFF (1011277) | more than 6 years ago | (#20172223)

## lame (0)

## Anonymous Coward | more than 6 years ago | (#20173181)

## Re:Some Reference info (1)

## Impy the Impiuos Imp (442658) | more than 6 years ago | (#20173183)

"Audience level" of various Slashdot articles:

- Traveling Salesman: Assume knows what P=?NP means, exponential complexity algorithms

- Badonkadonk: Assume reader doesn't even know yet women don't have weiners.

## Re:Some Reference info (0)

## Anonymous Coward | more than 6 years ago | (#20172329)

Thanks for your help. We really couldnt have managed to find that Wikipedia page by ourselves. Your internet skills are awesome.

## Re:Some Reference info (1)

## UbuntuDupe (970646) | more than 6 years ago | (#20173305)

## So (a real comment)... (5, Funny)

## LiquidCoooled (634315) | more than 6 years ago | (#20172035)

What is the optimum path the fibre fitter must take to lay all the cables and reduce his mileage?

## Re:So (a real comment)... (0)

## Anonymous Coward | more than 6 years ago | (#20172347)

-For an even number of cities, find a minimum weight perfect matching (polynomial time), add those edges to the graph, and use an Eulerian path as before.

## Re:So (a real comment)... (2, Funny)

## LiquidCoooled (634315) | more than 6 years ago | (#20172397)

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.

## And in other news (0, Offtopic)

## GrEp (89884) | more than 6 years ago | (#20172043)

## Slashdotted (0)

## Yusaku Godai (546058) | more than 6 years ago | (#20172047)

This looked cool too. Any mirrors (no pun intended)?

## Re:Slashdotted (1)

## Yusaku Godai (546058) | more than 6 years ago | (#20172387)

## Not the first time this has been proposed (4, Interesting)

## jfengel (409917) | more than 6 years ago | (#20172049)

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 (4, Interesting)

## PhysicsPhil (880677) | more than 6 years ago | (#20172269)

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 (4, Insightful)

## mdmkolbe (944892) | more than 6 years ago | (#20172337)

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 (5, Interesting)

## SeanMon (929653) | more than 6 years ago | (#20172747)

1.25 x 10^167 yearsto generate 100^100 photons.Just a bit more than we can handle.

## Re:Not the first time this has been proposed (2, Funny)

## Climate Shill (1039098) | more than 6 years ago | (#20173001)

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:Not the first time this has been proposed (1)

## mr_mischief (456295) | more than 6 years ago | (#20173511)

Still, they say that for larger problem sets the SNR makes detection and filtering too difficult. Larger problem sets are precisely where one worries the most about computational complexity, of course. So it's still, at least for now, just a neat trick.

## First Thoughts (5, Funny)

## TheRequiem13 (978749) | more than 6 years ago | (#20172057)

Gasundheit!

## Re:First Thoughts (4, Informative)

## codeButcher (223668) | more than 6 years ago | (#20172123)

Yes, I believe it should have been

Gedankeneksperiment [leo.org] , with a capital G.Freundliche Grüße,

Your friendly neighbourbood grammar Nazi

## GRB explanation (5, Funny)

## a.d.venturer (107354) | more than 6 years ago | (#20172085)

to which Charles Stross replies "Ah, so that's what the short duration GRBs are!"

Fnord.

## You've exceeded Slashdot's DMR (3, Funny)

## spun (1352) | more than 6 years ago | (#20172379)

## Re:You've exceeded Slashdot's DMR (1)

## Boronx (228853) | more than 6 years ago | (#20172745)

## Re:You've exceeded Slashdot's DMR (1)

## spun (1352) | more than 6 years ago | (#20173049)

## Re:You've exceeded Slashdot's DMR (1)

## Impy the Impiuos Imp (442658) | more than 6 years ago | (#20173257)

- Quantum Computing

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

Slashdot reader: Who is Charles Stross?

- Women

"She wears an over the shoulder boulder holder..."

Slashdot reader: "She?"

## Gedankenexperiment ? (1)

## OpenSourced (323149) | more than 6 years ago | (#20172119)

## Re:Gedankenexperiment ? (1)

## PeterBrett (780946) | more than 6 years ago | (#20172551)

## Re:Gedankenexperiment ? (1)

## OpenSourced (323149) | more than 6 years ago | (#20173345)

No, it's watching at die Blinkenlichten, silly!Uhm. I wonder how many people outside Slashdot would understand this exchange

## Turing Machine vs Laws of Physics (2, Insightful)

## TheEmptySet (1060334) | more than 6 years ago | (#20172137)

## Parent post is not correct. (1)

## serviscope_minor (664417) | more than 6 years ago | (#20172913)

## Not sure I agree (1)

## TheEmptySet (1060334) | more than 6 years ago | (#20173085)

## A general summary of the article (5, Informative)

## PhysicsPhil (880677) | more than 6 years ago | (#20172165)

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 (2, Insightful)

## gr8_phk (621180) | more than 6 years ago | (#20172385)

## Re:The run time is wrong (3, Funny)

## SamP2 (1097897) | more than 6 years ago | (#20173107)

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 (2, Insightful)

## Geoffrey.landis (926948) | more than 6 years ago | (#20172393)

stillscale 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 (1)

## atamyrat (980611) | more than 6 years ago | (#20172409)

Shortest path is about finding shortest route between two nodes in graph, wihle TSP is about traveling each node exactly once with minimum cost.

## Re:A general summary of the article (0)

## Anonymous Coward | more than 6 years ago | (#20172545)

## Re:A general summary of the article (5, Interesting)

## Bender0x7D1 (536254) | more than 6 years ago | (#20172557)

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.

## Re:A general summary of the article (1)

## Kupek (75469) | more than 6 years ago | (#20173587)

can, it's just not useful. If I state a problem is O(something), I get to determine what operation I counted. But if we're talking about sorting, and I choose any operation other than comparing two elements, then it's not a useful analysis.## NP != "Non-polynomial" (5, Informative)

## imasu (1008081) | more than 6 years ago | (#20172179)

## Re:NP != "Non-polynomial" (5, Informative)

## The Night Watchman (170430) | more than 6 years ago | (#20172521)

thatpoint 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" (5, Informative)

## teknopurge (199509) | more than 6 years ago | (#20172607)

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 (4, Insightful)

## n01 (693310) | more than 6 years ago | (#20172219)

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.

## Re:Still an exponential algorithm (1)

## pclminion (145572) | more than 6 years ago | (#20172567)

Since the speed of light is finite, the algorithm still takes O(2^N) i.e. exponential time to complete.Yes, but at least in theory the paths can be made almost infinitely short. At some point the energy density of the photons will overwhelm spacetime and form a black hole, however :-)

## Re:Still an exponential algorithm (1)

## n01 (693310) | more than 6 years ago | (#20173601)

## exponential photons == not practical (4, Insightful)

## frankie (91710) | more than 6 years ago | (#20172275)

## Re:exponential photons == not practical (2, Insightful)

## Cyclon (900781) | more than 6 years ago | (#20172511)

The proposed method is meant purely as a gedankenexperiment.Guess you missed this part.

## Re:exponential photons == not practical (0)

## Anonymous Coward | more than 6 years ago | (#20172895)

## Re:exponential photons == not practical (4, Funny)

## RealAlaskan (576404) | more than 6 years ago | (#20172969)

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

## Does this mean you can make "maps" (0)

## Anonymous Coward | more than 6 years ago | (#20172373)

## P= NP (2, Funny)

## naoursla (99850) | more than 6 years ago | (#20172417)

The researchers are just using an expoential number of photons to aid in the processing.

## Wow, you're dumb (0, Flamebait)

## Anonymous Coward | more than 6 years ago | (#20172705)

## Mad moderation. (2, Funny)

## serviscope_minor (664417) | more than 6 years ago | (#20172975)

Please, mods use some sense in moderating.

## Re:Mad moderation. (1)

## naoursla (99850) | more than 6 years ago | (#20173419)

And it is true that if you have expoentially increasing computational resources you can solve NP problems in polynomial time.

## Poor server... (1)

## tool462 (677306) | more than 6 years ago | (#20172495)

## Oh great. (1)

## tietokone-olmi (26595) | more than 6 years ago | (#20172581)

Which kind of tells why it's "purely a Gedankenexperiment".

## Polynomial time. (1)

## Climate Shill (1039098) | more than 6 years ago | (#20172587)

so any NP-complete problem can be solved in reasonable real time if you have exponential resources to throw at it. Which is what this optical solution does, with N^N photons. There may be some interesting techniques involved, but it's still basically "assume a big enough computer....".

## Reminds me of rainbow sort (1)

## mjsottile77 (867906) | more than 6 years ago | (#20172589)

## I prefer the "wet" method (1)

## SparkleMotion88 (1013083) | more than 6 years ago | (#20172611)

## My quack-o-meter is beeping (5, Informative)

## p3d0 (42270) | more than 6 years ago | (#20172619)

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:

## Re:My quack-o-meter is beeping (1)

## wurp (51446) | more than 6 years ago | (#20173105)

Non-polynomial wouldn't mean the same thing as NP... You could put together an algorithm that is non-polynomial on a non-deterministic computer, too, which would be non-polynomial and not NP. It would be harder than NP.

## Re:My quack-o-meter is beeping (2, Informative)

## p3d0 (42270) | more than 6 years ago | (#20173185)

## Re:My quack-o-meter is beeping (1)

## wurp (51446) | more than 6 years ago | (#20173493)

I really appreciate your forthright stand on what they had to say - it takes some confidence to tell someone who so clearly knows what they're doing in one technical area that they're full of shit in another.

## Josie Bauer addressed Travelling Salesman problem (3, Funny)

## karlandtanya (601084) | more than 6 years ago | (#20172685)

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

## Increasing Orders (2, Interesting)

## Doc Ruby (173196) | more than 6 years ago | (#20172695)

multiplication(2N): geometric increase, as is "N*X". "N*N" is calledexponential(NX). What is "NN" called? And is there a higher order of increase?And what are all those kinds of operations called?

## Re:Increasing Orders (1)

## tomstdenis (446163) | more than 6 years ago | (#20172929)

polynomial, N^N (or more so) c^N where c is constant is called exponential when c > 1.## Re:Increasing Orders (1)

## xenocide2 (231786) | more than 6 years ago | (#20173247)

## Re:Increasing Orders (1)

## Skuto (171945) | more than 6 years ago | (#20172947)

http://en.wikipedia.org/wiki/Tetration [wikipedia.org]

## Re:Increasing Orders (1)

## Jeek Elemental (976426) | more than 6 years ago | (#20173335)

## really 100^100 photons (1)

## cinnamon colbert (732724) | more than 6 years ago | (#20172837)

any comments from someone who understands this ?

## optics is not unususal (1)

## cinnamon colbert (732724) | more than 6 years ago | (#20172903)

## Analog computers (0)

## Anonymous Coward | more than 6 years ago | (#20172841)

Analog computer thought experiments to accomplish this were proposed long ago.

e.g. for finding the shortest path between cities: cut lengths of string corresponding to each possible route between cities, then tie them all together. Then just grab the two knots corresponding to origin and destination and pull them taught (you may need to cut any irrelevant strings that restrict this pulling)

See http://consc.net/notes/analog.html [consc.net] for more.

## Poor choice of domain name (2, Insightful)

## Anonymous Coward | more than 6 years ago | (#20172939)

I guess they were going for "optics express"

I of course read it as "optic sex press"

and there's no way you're getting me to click that link at work!

## This is sorta old (1)

## tjstork (137384) | more than 6 years ago | (#20172973)

## In other news... (1)

## Spazmania (174582) | more than 6 years ago | (#20173035)

I would note, however, that a more useful result does exist: many O(n log n) problems reduce to O(n) given the availability of log n processors. As log n is generally small this requires only a trivial application of parallelism. Merge sort, one of the staples of database engines, is a good example.

## Analog reference (1)

## samuel4242 (630369) | more than 6 years ago | (#20173059)

## The given algorithm is $O(2^N)$ (2, Insightful)

## natoochtoniket (763630) | more than 6 years ago | (#20173113)

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.

## glass map of london (1)

## Hubert_Shrump (256081) | more than 6 years ago | (#20173155)

http://www.rsc.org/publishing/journals/LC/article

## Finally, a solution is in sight (1)

## SleptThroughClass (1127287) | more than 6 years ago | (#20173189)

## Definition of gedankenexperiment (1)

## 192939495969798999 (58312) | more than 6 years ago | (#20173371)