# The Unapologetic Mathematician

## Still busy

I’ve now determined that the distance from here to the department is not as walkable as the same distance would be in New Haven.

As I recover, here is a paper on solving the Travelling Salesman Problem. The authors do so with “white light interferometry”, which sort of makes it a quantum computation algorithm.

The thing they’re overstating is this: this is far from the first reduction of an NP-complete problem to a polynomial-time solution. What they miss out on is that their algorithm is exponential in space — the amount of computational space required goes up exponentially with the size of the problem. Specifically, it takes $N^N$ photons to solve the $N$-city problem. Thus it’s not really that new as far as computational complexity goes. Still.

August 9, 2007 Posted by | Uncategorized | 6 Comments