Slashdot Mirror
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 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."
I think a couple of gaurd dogs and a shotgun are a good enough method to solve the travelling salesman problem.
I for one am welcomming our new briefcase carrying shiny shoes foot in the door encylopadea selling in most efficient manners overloads!
Will code for new sig.
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.
liqbase
(Did I mention how much I hated my Computability and Complexity courses when I was in college?)
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).
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
The rock, the vulture, and the chain
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?
liqbase
And in other news kdawson announces that will be leaving Slashdot become the new editor in chief of World Weekly News
bash-2.04$
bash-2.04$yes "Don't you hate dialup connections?"| write USERNAME
Damn. 5 comments and it's already slashdotted.
This looked cool too. Any mirrors (no pun intended)?
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.
...gedankenexperiment...Gasundheit!
What?
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.
Is that something like watching at the blinkenlights?
Rome taught me patience and assiduous application to detail. Virtues which temper the boldness of great, general views.
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.
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.
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.
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.
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.
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?
That joke has too high of a Dennis Miller ratio even for Slashdot.
- None can love freedom heartily, but good men; the rest love not freedom, but license. -- John Milton
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.
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".
http://www.geoffreylandis.com
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.
The submitter should have gedanken about their server before submitting this story.
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".
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....".
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). Again, a clever thought experiment - not sure how feasible it will be anytime soon to actually use though.
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
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.
Patrick Doyle
I mod down every jackass who puts his moderation policy in his sig. Oh, wait a sec....
Solution involved a Farmer's daughter, which she apparently was.
"Reality is that which, when you stop believing in it, it doesn't go away." - Philip K. Dick
"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?
--
make install -not war
Go read this and note how stupid your comment makes you look.
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 ?
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 for more.
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.
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.
SJW n. One who posts facts.
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!
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.
This is my sig.
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.
SJW n. One who posts facts.
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.
Moderating "-1, Disagree" is simple censorship. Have the guts to post your opinion.
My favorite analog computing paper comes from Steiglitz et al see www.cs.princeton.edu/~ken . 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.
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...
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.
someone else already did it, much more simply, in 2002.
. asp?doi=b200589a
http://www.rsc.org/publishing/journals/LC/article
Keep your packets off my GNU/Girlfriend!
no pics in your link :(
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.
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.
stuff |
Also I don't see (from the abstract) how they're going to extract the desired shortest answer from all the wrong answers and reflections.
It'd be a little like having an polynomial time algorithm that required exponential space. Interesting oddity, but unfortunately not useful in itself.
"Not an actor, but he plays one on TV."
Any article adds loads of scholarly credibility by quoting from wikipedia.
You can improve the algorithm to go from exponential to constant time (ignoring the finiteness of the speed of light) if you don't apply the optical setup to the TSP, but to the existence of a http://en.wikipedia.org/wiki/Hamiltonian_path or circle, in a given input graph, which is still NP-Complete.
You can make sure a photon has passed through every node exactly once if you put power of two delays in every node. If the delays sum up to 111....111 (in binary notation) a Hamiltonian exists. Big plus: you're done with only one measurement.
who read the url as 'optic sex press'?!
Just because an idea is popular doesn't make it right.
And I was thinking, "It should be Optical Sex Press!"
echo 'cat sig | sh' > sig
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'.
My stupid web site
To our knowledge it is the first time that a method for the reduction of non-polynomial[sic] time to quadratic time has been proposed.
Let n = number of cities.
1. Cut strings to length of path between cities: O(n^2))
2. Tie together ends of links that meet at same city: O(n^2))
3. Grab start and destination endpoints in each hand, and pull taut: O(1)
4. Mark route along links that have tension in them: O(n)
Overall complexity: O(n^2)
http://www.xkcd.com/207/
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.
Quattuor res in hoc mundo sanctae sunt: libri, liberi, libertas et liberalitas.
Damn you, that's pretty much exactly what I was about to post. I miss the Scientific American "Mathematical Games" column, which is where I first ran into this scheme.
I thought that Martin Gardner argued that step to was combinatorial, so proportional to N! not N^2.
In either case, it seems to be equivalent to the scheme in teh article.
I'm one of Jehovah's Witnesses, you insensitive clod!
As a former imaginary traveling salesman, I beg you slashdotters to show some mercy.
Let's get this straight. To solve the traveling salesman problem, we make a big fiber optic thingy and shine a flashlight down the fibers. The interference pattern gives us the answer.
But it's not a computer any more. And it's not something that "runs on photons" as many commenters have said. Nope. These patterns happen because of quantum effects, which mean the little virtual photons are doing all the work.
So that's the plan, eh? Make the little virtual photons find the salesman? Well I've got news for you, Mr. Big Shot Scientist. Next year we're sending out an army of virtual traveling salesmen. That'll show ya!
So we have quantum computers that are doing work in other universes and virtual flashlights finding the best paths for salesmen? I'm thinking this whole traveling salesman gig is just getting too hard any more. I'm going to look into working for RIAA.
...Although I suspect there may be a slightly faster algorithm.
Huh ? How is N^N polynomial time ? N^M is polynomial for /fixed/ M. N^N is much larger than polynomial time.
Then this would be a really good algorithm. You have a colleague in each town put up a set of beamsplitters which correspond to the roads connecting his city to the others, and (approximately) tada!
You've got a lot more than your citations to worry about if you're a physicist and don't know what a quantum computer is. The point of giving such a definition is for clarification... it doesn't introduce any new knowledge to the intended audience (except for maybe casual readers from other fields) it just crystallizes what is already known into something useful and concise. They could have just as well made up a definition for scratch. It doesn't matter. There is ZERO risk that relying on wiki for the definition would introduce a flaw into their results. There is admittedly a lot of debate in academia over wikipedia... a lot of people hate it, not least of which because wiki's "no original research" policy seems to give the finger to people who are aren't exactly humble about their wealth of knowledge. But I've known quite a few professors who have used wiki to give background for their presentations, colloquiums, etc., and to me it just seems rather needlessly stuck-up to say "It is never ever ever ok to cite Wikipedia, because we don't like it!"
When things get complex, multiply by the complex conjugate.
I know I have no clue what it means. NP complete? It's one of those happy buzz phrases geeks toss around to sound cool. Come on now, how many of you have no idea or looked it up on wikipedia?
Isn't he just solving a NP polynomial problem with... a nondeterministic machine? So what? I can do that too...
Isn't using N^N photons similar to using N^N salesmen?
The first sentence of the introduction claims TSP is an unsolved problem.
TSP is not unsolved.
The third sentence of the introduction claims that NP-complete problems take more than polynomial time. NP-complete problems all have solutions on a non-deterministic Turing machine that can complete within polynomial time. Whether or not they have any solutions on a deterministic Turing machine that can complete within polynomial time is considered to be an unsolved problem.
Is "Optics Express" a refereed journal?
On a similar note, I wrote an article last year about solving the Subset Sum problem (another NP-complete problem) using optics. This solution involves summing modulated sine waves and using an optical Fourier transform to determine which sums are contained within the set. An interesting read if you want a different slant on the topic...
My work is in the Real Estate Industry. My FIRST tasking of the day is to visit the houses that have come on to the market. Sometimes it is 1 or 2, or it has gone as high as 30 to 40; And about 99% of the time, some place different than before. My current method is to screen scrape MapQuest for directions, and distances. It sure would be nice to use an algorithm that could get the job done; I also think the Web Master at MapQuest would like it to, so that the rest of my kind could use it.
It was a paper about the hamiltonian path problem, where the authors have reached the same conclusion: that they require an exponential amount of energy... I've googleit and I've found the author page: http://www.cs.ubbcluj.ro/~moltean/publications.htm
and the paper was:
http://www.cs.ubbcluj.ro/~moltean/nc_oltean.pdf
Probably nobody read this storya anymore but parent describes the problem with the method in the easiest and most obvious way. ...but I cant resist saying that in the Paper they say that "other choices are possible" about the delay lines... I cant tell if there are any other ways to choose delay lines that are not exponential.
Can they use this appuratus to solve the Flodded Server Problem also?
crahso(s^2) > x where 's' is the number of slashdotters.
Table-ized A.I.
Hit some nails in a block of wood, representing the cities. Carve the roads between the cities as trenches between the nails. Pour some "magnetic" fluid of a certain thickness in the trenches and wait for it to settle.