## Another possible solution to an NP-complete problem?

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-complete problems can be turned into other kinds of NP-complete problems by applying a polynomial-time reduction algorithm. For example, it is possible to convert a degree constrained spanning tree, or a string to string problem into a knapsack problem... If we can find a sufficiently elaborate solution to one kind of NP-complete problem, and it is feasible to turn other kinds of NP-complete problems into the kind of problem we have a clever solution for, then it stands to reason that we have a very good shot at solving the problem that we don't have a direct, clever solution for.

This has some security implications.

I'd like to pull in something that's been fascinating me for a while, something that gave me the notion to write this article called a zero knowledge proof. As the name implies, it is a way to prove that you know a secret without revealing what that secret is. The canonical example of this is a circular cave with a magick door at the farthest point, but there are others that are less well known, such as proving to someone who is color blind that two differently colored balls are, in fact, different colors withouts saying what they are or proving that n people know the same magick number by picking cards out of the same ordered pack with their hands in a bag. The ZKP I keep thinking of involves a Hamiltonian cycle for a very large graph: Say that you and I both know a very large graph called G (we wrote it on a napkin at the club last night and it has a couple of thousand vertices), and I want to prove that I know a Hamiltonian cycle to traverse that graph without giving away the graph. This, incidentally, would prove my identity if you were otherwise unable to recognize me. So, you and I agree to play ten rounds of a game. In each round I make a copy of the graph and change the names of all of the vertices. For the sake of argument instead of numbering them I give them all names of characters from Babylon-5 or Unicode characters and call the resultant graph H. The configuration of the graph doesn't change, just the names. I commit to using H irreversibly somehow (say, you hold a gun to my head). You ask me to either show you the corresponding Hamiltonian cycle through H (I do so, and because it's trivial to test the answer to an NP-complete problem you verify that it's a legit Hamiltonian cycle), or you ask me to show you how to turn the graph G that you already know into the graph H (which I do, because I remember how I renamed the vertices). At no time do either of us give away the specifics of the original Hamiltonian cycle for G. Due to the fact that Hamiltonian cycles are NP-complete, there is a vanishingly small chance that I can successfully lie to you each and every round (for n rounds of the game, the probability of successfully lying each and every time is 1/(2n)), and if you catch me in a lie, you shoot me. You and I might be able to do this ten rounds in a row if we're sufficiently motivated. Computers can do this thousands of times in a row, thus making the probability of an attacker lying successfully vanishingly small, indeed.