The Unapologetic Mathematician

Mathematics for the interested outsider

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



Get every new post delivered to your Inbox.

Join 391 other followers