Beta

Slashdot: News for Nerds

×

Welcome to the Slashdot Beta site -- learn more here. Use the link in the footer or click here to return to the Classic version of Slashdot.

Thank you!

Before you choose to head back to the Classic look of the site, we'd appreciate it if you share your thoughts on the Beta; your feedback is what drives our ongoing development.

Beta is different and we value you taking the time to try it out. Please take a look at the changes we've made in Beta and  learn more about it. Thanks for reading, and for making the site better!

Optical Solution For an NP-Complete Problem?

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

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

cancel ×

232 comments

Better solution... (5, Funny)

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

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

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

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

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:Better solution... (0)

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

Just make sure he's not a burglar [youtube.com] first

I for one (2, Funny)

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

I for one am welcomming our new briefcase carrying shiny shoes foot in the door encylopadea selling in most efficient manners overloads!

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

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

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

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

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

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

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

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

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

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

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

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

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 using 2^N or so). In effect, each photon is used to perform one 'calculation', in some sense. Or at least that is what I understand from TFA, IANA Physicist.

Re:Parallel computing (1)

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

Exactly. Algorithmically, this is nothing. They're just saying, "What if we had hardware that could perform an unlimited number of calculations simultaneously, and thus render time-complexity of certain algorithms irrelevant?" To which I say: "That would be spiffy, but you don't have such hardware, and Heisenberg says you never will."

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)

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

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

This is /. not "CNN News", I think it's reasonable to expect readers here to know what The TSP is.

Re:Some Reference info (0)

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

or be able to look it up on Wikipedia for themselves.

Re:Some Reference info (2, Interesting)

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

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

Wikipedia is a great reference for getting a quick understanding of a subject. It's obviously not the same as years of study or work in related fields to that subject. I wasn't surprised to find that the best (imho) links for info on what this article was about were from Wikipedia - yeah it would have been cooler to link some obscure website or reference - but honestly I would rather that some background info/reference links had just been in the summary so that when I went to the abstract I at least knew what I was getting into.

Re:Some Reference info (1)

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

So in fact it's more of an analog quantum computer, something like Babbage machine of quantum computers?

Re:Some Reference info (2, Informative)

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

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

Re:Some Reference info (1)

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

but generally too lazy... thus the ready supply of mods for the obvious link.

Re:Some Reference info (2, Insightful)

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

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:Some Reference info (5, Funny)

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

Badonkadonkexperiment [wikipedia.org] ???

lame (0)

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

no pics in your link :(

Re:Some Reference info (1)

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

Now that's something Slashdot readers need a hell of a lot more education in.

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

Golly Gee Wickers, Mister!

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)

Gedankenexperiment: When you want to use German, and can't come up with a reason, Gedankenexperiment is for YOU! (tm)

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

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

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:So (a real comment)... (0)

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

-For an odd number of cities, pick any Eulerian path, they all have the same length.
-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)

You just don't get it...
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)

And in other news kdawson announces that will be leaving Slashdot become the new editor in chief of World Weekly News [wikipedia.org]

Slashdotted (0)

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

Damn. 5 comments and it's already slashdotted.
This looked cool too. Any mirrors (no pun intended)?

Re:Slashdotted (1)

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

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

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

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

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

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

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

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.

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)

Good thing they were talking about a single photon being split and traveling all possible paths simultaneously, and measuring the interference, then.

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)

...gedankenexperiment...

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)

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

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

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

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

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

That's only because he abbreviated GRB.

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

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

Sad to say, although I know what a GRB is I had to look up who the heck Charles Stross is. He sounds like my kind of author, but it makes me wonder: are all good sci-fi authors from the UK these days? Iain Banks, Ken McLeod, Stephen Baxter, Peter Hamilton, Ian McDonald: the list goes on and on.

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

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

Dennis Miller Ratios for various Slashdot topics:

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

Is that something like watching at the blinkenlights?

Re:Gedankenexperiment ? (1)

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

No, it's watching at die Blinkenlichten, silly!

Re:Gedankenexperiment ? (1)

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

Gedankenexperiment ? Is that something like watching at the blinkenlights?
No, it's watching at die Blinkenlichten, silly! ...
Uhm. I wonder how many people outside Slashdot would understand this exchange :o)

Turing Machine vs Laws of Physics (2, Insightful)

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

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 P=NP, which would say that a Turing maching can after all achieve similar efficiency.

Parent post is not correct. (1)

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

You are confused about the definition of a Turing machine. A Turing machine says nothing about computational efficiency. Being able to solve NP complete problems in polynomial time will not give you an oracle. That is, it will still not be able to solve the halting problem, for instance.

Not sure I agree (1)

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

You're probably right that it won't give you an oracle, but my comment is about the properties of a Turing machine (or similarly any computer based on the same algorithmic logic) as regards runtime orders. There are many applications (unlike NP) in which one can prove useful lower bounds for runtime. However, I don't think it goes against causality or thermodynamics to beat these by getting some funky physical process to come up with the answer in a way that avoids the necessary computation by 'outsourcing' it to the 'processing' that is the underlying cause of the laws of physics. Okay, so this is a bit wacky, but what the hell. I am a mathematician...

A general summary of the article (5, Informative)

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

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

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

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

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

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

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

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

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

I couldn't RTFA (slashdotted??), but, from what you describe, it seems it is shortest path problem, not TSP.

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)

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).
They disconnect one of the connections between the exit node and a node connecting to the exit node, decrease the length of the reference arm by the distance of that connection, and make the connecting node the new exit node. If the reference signal still interferes, then the new exit node is the correct second-to-last hop in the path. If not, then they just try the other cities connected to the original exit node until they find the correct one.

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)

Well, you 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)

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

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

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

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

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

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

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.

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)

Yes, but at least in theory the paths can be made almost infinitely short.
No you can't because the 'algorithm' sums powers of two length to make sure every node was visited exactly once. If you make variable a arbitrarily small, imprecisions sum up, and you can't be sure any more that every node was visited exactly once.

exponential photons == not practical (4, Insightful)

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

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

Don't you mean "exponential photons != practical"? :)

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)

based on other things? For example, the Kemeny order in voting is NP-hard. If you were to make the appropriate map, would it solve the problem for a couple of dozen rank-ordered presidential candidates?

P= NP (2, Funny)

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

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.

Wow, you're dumb (0, Flamebait)

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

Go read this [wikipedia.org] and note how stupid your comment makes you look.

Mad moderation. (2, Funny)

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

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.

Re:Mad moderation. (1)

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

It was intended more as a thought provoking joke, really.

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)

The submitter should have gedanken about their server before submitting this story.

Oh great. (1)

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

Another one of these Gedankenexperiments that end up (if they were feasible to implement in the real world) trading time for space. Of course if we're dealing with photons and stuff, that "space" ends up being real, physical space rather than bits in a memory chip somewhere.

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

Polynomial time. (1)

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

IIRC the word "time" as used in "exponential time" etc. actually means the amount of work done,
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)

This reminds me of a clever optical sorting algorithm I ran across a paper on in recent years (see http://www.cs.auckland.ac.nz/CDMTCS//researchrepor ts/244dominik.html [auckland.ac.nz] ). Again, a clever thought experiment - not sure how feasible it will be anytime soon to actually use though.

I prefer the "wet" method (1)

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

This problem seems to lend itself very well to creative solutions. Perhaps because it is pretty simple and it readily corresponds with many geometric/structural systems that can be used to compute a solution. As far as I know, this was the first problem that was solved using DNA [jyi.org]

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

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

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.

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

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

I agree with everything you have to say, with one nitpicking exception: non-polynomial time seems a reasonable term to use. An algorithm that is O(N^N) takes time that is not polynomial in N, hence it is non-polynomial time.

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)

I agree with everything you have to say, with one nitpicking exception: non-polynomial time seems a reasonable term to use. An algorithm that is O(N^N) takes time that is not polynomial in N, hence it is non-polynomial time.
I disagree. They're not talking about an algorithm here; they're talking about the Traveling Salesman Problem. They called the TSP "non-polynomial", and that is by no means certain. If you could prove that the TSP has no polynomial-time solution, you'd get the Turing award.

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

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

Yeah, I wasn't trying to say it was reasonable to use in that context... you just said "there's no such thing as non-polynomial time". It was with that specific assertion that I was disagreeing.

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)

Some time ago.


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

Increasing Orders (2, Interesting)

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

"N+X" is called "addition": additive increase. "N+N" is called multiplication (2N): geometric increase, as is "N*X". "N*N" is called exponential (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)

N*N is called a quadratic and it's 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)

Note that realistically, pretty much any problem has an exponential solution, so going beyond this isn't very interesting. There's a few problems related to the halting problem for which we know we simply can't provide a running time, and a couple other classes of problems that we don't know how to analyze, but they're not what I'd call real world problems. These facts, have, naturally, not stopped mathematicians from spending time talking about how to represent very large numbers; the Ackerman function is one such example.

Re:Increasing Orders (1)

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

Tetration

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

Re:Increasing Orders (1)

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

dear lord that made neurons I thought Id beaten into submission years ago move.

really 100^100 photons (1)

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

haven't been able to read the /.ed article, but I speculate that it is quite possible they could use a lot less then 100^100 photons
any comments from someone who understands this ?

optics is not unususal (1)

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

if you look at the references in the article, several of the titles suggest that the use of optical means to solve the traveling salesman problem is not new, altho the exact optical setup here is new.

Analog computers (0)

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

Their claim that "it is the first time that a method for the reduction of non-polynomial time to quadratic time has been proposed" is pretty sceptical.

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)

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

I have in one of my numerical methods books, dating from I want to say the early 1990s, a fairly lengthy discussion on how an analog computer made out of a rope could theoretically be used to solve TSP. The point, and honestly, I might not understand this correctly, was that computational complexity is a function of computers being based on a Turing model. So, an analog "computer" you could dream up could theoretically "solve" TSP, because, it's really not the same sort of machine. But it would never solve it exactly... per se.

In other news... (1)

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

In other news, Computer Science researchers discover that O(n^n) problems reduce to O(1) given the availability of n^n comptuers working in parallel.

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)

My favorite analog computing paper comes from Steiglitz et al see www.cs.princeton.edu/~ken [google.com] . I like the way to use car differentials to solve 3SAT. Pretty cool. It only requires O(n) differential equations where n is the number of clauses in the 3SAT equation. But I've heard that the result still requires an exponential amount of precision. At least according to some. Maybe an engineer could hack through what baffles the theory heads.

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.

Finally, a solution is in sight (1)

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

Finally someone will shine some light on this problem. Unfortunately, the answer is only "a photon". I hope it tells you which photon and the path.

Definition of gedankenexperiment (1)

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

This is where you read a summary like that one, and you want to gedanken yourself in the head with a hammer afterwards for trying to understand it.
Load More Comments
Slashdot Account

Need an Account?

Forgot your password?

Don't worry, we never post anything without your permission.

Submission Text Formatting Tips

We support a small subset of HTML, namely these tags:

  • b
  • i
  • p
  • br
  • a
  • ol
  • ul
  • li
  • dl
  • dt
  • dd
  • em
  • strong
  • tt
  • blockquote
  • div
  • quote
  • ecode

"ecode" can be used for code snippets, for example:

<ecode>    while(1) { do_something(); } </ecode>
Create a Slashdot Account

Loading...