Optical Solution For an NP-Complete Problem?

6 writes to let us know that two optical researchers have proposed, as a thought experiment, a novel idea for solving the traveling salesman problem. From the abstract: We introduce an optical method based on white light interferometry in order to solve the well-known NP-complete traveling salesman problem. To our knowledge it is the first time that a method for the reduction of non-polynomial time to quadratic time has been proposed. We will show that this achievement is limited by the number of available photons for solving the problem. It will turn out that this number of photons is proportional to N^N for a traveling salesman problem with N cities and that for large numbers of cities the method in practice therefore is limited by the signal-to-noise ratio. The proposed method is meant purely as a gedankenexperiment."

Comments

Some Reference info

[Fox_1]

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

Re:Some Reference info

[faragon]

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

Re:First Thoughts

[codeButcher]

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

Freundliche Grüße,

Your friendly neighbourbood grammar Nazi

A general summary of the article

[PhysicsPhil]

I browsed through the article, and here is my understanding of what they are doing.

The experimenters are constructing the map of the various cities using optical fibres. Each city represents a junction in the optical fibre network, and each fibre has a length proportional to the weight of the edge joining two cities in the abstract problem.

Once the fibre network is constructed, they shine a white light source into the network. As the light propagates through the system, it splits at each junction (i.e. city). As a consequence, the optical signal is able to sample all possible paths through the network simultaneously. The entire optical network is put on one arm of an interferometer, and the length of the other arm (the reference arm) is adjusted. Starting from a known lower bound on the city length, the length of the reference arm is increased until the reference signal interferes with the output signal from the optical network. At that point, they have the length of the shortest path, and apparently can do some kind of reconstruction to get the actual path from there (didn't quite follow how that happened).

The claimed reduction of an NP problem to quadratic comes from the setup of the experimental apparatus. An "operation" consists of connecting one of the N cities to another of the N cities. For an average collection of cities, there will be a number of roads/connections proportional to N^2. Of course the operation is awfully slow, but it's a thought experiment more than anything.

NP != "Non-polynomial"

[imasu]

First off, NP does not mean "non-polynomial", it means "nondeterministically polynomial". Which means, the set of problems that can be solved in polynomial time on a nondeterministic turing machine. They are not reducing an NP problem to P here, which would require that their algorithm be executable on a deterministic turing machine in polynomial time. Rather, they are saying that if they effectively simulate a limited nondeterministic turing machine by increasing the number of compute units (in this case, photons) to effectively infinite numbers, then there is a polynomial solution. Which, since the travelling salesman problem is known to be in NP, is not surprising. Or am I misreading this? What IS cool is that they have found a way to actually effectively simulate a subset of a nondeterministic turing machine.

Re:NP != "Non-polynomial"

[The Night Watchman]

Rather, they are saying that if they effectively simulate a limited nondeterministic turing machine by increasing the number of compute units (in this case, photons) to effectively infinite numbers, then there is a polynomial solution. Which, since the travelling salesman problem is known to be in NP, is not surprising. Or am I misreading this? That sounds right to me. I don't like how they're claiming that "the complexity of the traveling salesman problem can be dramatically reduced from N! to N^2 by optical means." They're not reducing the complexity of the problem at all. What they're doing is designing a parallel processing system that can approximate a nondeterministic Turing machine, thereby allowing the problem to be solved in polynomial time. This does nothing to indicate that P=NP. While they do make that point clear, I still take issue with their claim that they're doing anything at all to the complexity of the original problem.

Re:NP != "Non-polynomial"

[teknopurge]

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

IMO, the only way to reduce NP-Complete problems is using something like quantum entanglement or another similar characteristic that is not bounded by classical physics.

Re:NP != "Non-polynomial"

[Anonymous Coward]

Factoring integers has not been proven to be NP Complete

Re:NP != "Non-polynomial"

[cpeikert]

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

Re:Parallel computing

[CaptainPatent]

So effectively each photon is a CPU core and the running time is reduced by massive parallel computing rather than inherent reduction in complexity, which is (N^N)*(N^2). No. While the language of the paper is indeed rather thick, it seems they are using interference to get individual photons of light to traverse every pathway simultaneously. Even if I am only partially correct there, the photons in the experiment are only detected and are never being used as an instrument for computation.

My quack-o-meter is beeping

[p3d0]

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

Also, "NP" doesn't stand for "non-polynomial". There is no such thing as "non-polynomial time". It's Nondeterministic Polynomial time.

These guys may know their optics, but they're amateurs in complexity theory. This is most painfully obvious in their concluding sentence:

Since for practical (non-pathological) problems by purely electronic means very good solutions to even large size problems can be found, our proposed method is not meant to solve real-world traveling salesman problems but rather as a gedankenexperiment to show how photons and the laws of physics can considerably reduce the computational complexity of difficult mathematical problems. It does no such thing. All it does is parallelize the computation.

Re:My quack-o-meter is beeping

[p3d0]

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:Parent post is not correct.

[asuffield]

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 solves NP problems in polynomial time, but we don't currently know how to build one.

Quantum computers may or may not be such a machine - we're really not sure yet (possible proofs have been advanced for both answers; the prevailing opinion is that none of them are likely to be correct and quantum computers are something entirely new that we don't understand). Other methods of computation also may exist. Our understanding of the fundamental laws of physics is grossly incomplete, so we can't tell. However, it seems unlikely that the computational capacity of the universe is adequately modelled by a Turing machine.

This relates to the question of "P=NP?" as follows: if such a machine can be built, then *some* machines can solve these problems in polynomial time. If P=NP, then *all* machines can solve these problems in polynomial time.

Re:So (a real comment)...

[evanbd]

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