Another possible solution to an NP-complete problem?
Antarctica Starts Here. » Antarctica Starts Here. 2014-04-23
Summary:
A couple of days ago a research team comprised of faculty at Nanyang Technological University in Singapore, the University of Southampton in the UK, and IQFR-CSIC in Madrid, Spain published a paper containing a creative solution to a problem known to be NP-complete, namely a version of the traveling salesman problem. The TSP, in summary, postulates a scenario in which you have an arbitrary number of towns spread over a large area and an arbitrary number of paths connecting them. What is the shortest possible path one can take in which the traveler visits each town only once and returns to the point of origin? The answer is not a simple one, and in scenarios larger than a couple of towns (or nodes in a graph) the number of possible combinations rapidly balloons out of control. There are different strategies for finding the optimal path; brute force (trying every possible path) is guaranteed to work but the amount of time required to do so makes it prohibitive past a trivial number of nodes. Try it with a modest sized graph of only twenty towns and you may as well give up unless you want to try a more arcane technique like the Held-Karp or branch-and-bound algorithms. There are techniques to solve the TSP but several of the most feasible are very processor intensive (one required a 110 system cluster, and all of them count their CPU time in the tens of years). So, hamiltonian network problems are nothing to sneeze at.
The research team set up a network of optical fibres and couplers several kilometers in size which represented a set of five towns and the roads connecting them. The length of each optical fibre was precisely calibrated to introduce a unique and measurable delay in the transmission of light through the network. You could think of it like numbering vertices in a graph to identify them. After assembly, the experiment consisted of transmitting pulses of light into the network of optical fibers. As photons are wont to do, when presented with a set of possible paths they follow all of them simultaneously and thus traversed every coupler in the network. Due to the fact that you can add up the delays incurred by each path through the network the researchers successfully predicted when the first pulse would exit the network of optical fibers, which proved by performance that the network was Hamiltonian in nature, and that the most optimal solution had been determined for it. In a cryptographic sense the experiment is an oracle - put a question in, get an answer out that you can then do something useful with (like verify it).
But... why do we care? What's so important about being able to find the shortest path through a network?As I mentioned earlier, Hamiltonian paths are NP-complete, NP meaning "nondeterministic polynomial." Nondeterministic means that every time you try to find a solution you'll probably generate a different one; it may not be the most optimal solution and the specifics of the process might vary from solution to solution, but every possible solution is equally valid. Polynomial stands for polynomial time, or the amount of time an algorithm can take to run to completion when a particular set of inputs are taken into account. Without going into too much detail, the number of steps required to solve polynomial time problems can be estimated with the figure nk, where n is the complexity of the input. Verifying the answers is computationally easy. Actually arriving at the answers, however, is what mathematicians and computer scientists like to call hard. I spent some time trying to come up with a suitably hyperbolic way of expressing what hard means, and I can't think of one that doesn't do more harm than good to the point. Suffice it to say that "forget it" works. These are the sorts of problems that we ordinarily say would take sagans of years to solve by applying the best known available algorithms to them. Contrast this with problems in P (polynomial time), which means that it is relatively computationally easy to find the answers as well as check them.
But what does this mean? There is a theorem (that I don't begin to understand more than the executive summary of) that proves that different kinds of NP-co