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.

About these ads

August 9, 2007 - Posted by | Uncategorized

6 Comments »

  1. The authors point out the thing you’re complaining about right there in the abstract. They even say “The proposed method is meant purely as a gedankenexperiment.” Apparently gedankenexperiments impress reviewers, tenure committees, etc. more than thought experiments. (One might also note that the authors are German.)

    On the other hand, they do refer to time complexity as “complexity”, in the conclusion; one thinks that their heads are too clouded by the idea of winning the million dollars by proving P is not equal to NP, which if I’m not mistaken is a statement about time complexity.

    Comment by Isabel | August 10, 2007 | Reply

  2. They do say that, but they also say that this is the first time they know of a “non-polynomial” problem being reduced to a quadratic algorithm. Besides the sloppy use of terminology, this is plainly false. Many problems have quadratic algorithms, at the cost of taking exponentially much space.

    Comment by John Armstrong | August 10, 2007 | Reply

  3. Why do you use the British spelling of Travelling ? Just curious.

    Comment by Michael D. Cassidy | August 20, 2007 | Reply

  4. It looks better. “Traveling” is.. a bit thin.

    Comment by John Armstrong | August 20, 2007 | Reply

  5. I dislike the first two paragraphs: “1 followed by 80 zeros” “the same order of magnitude as the total number of atoms in the known universe” “So, should he give up?”

    How about just giving the algorithm; I think anyone reading about Traveling Salesmen and NP Hardness etc doesn’t need to read about 1 followed by 80 zeros; unless of cause they are the farmers daughter wondering when he’s showing up.

    Comment by Michael D. Cassidy | August 21, 2007 | Reply

  6. There are a lot of these papers out there that give much more background than is strictly needed. It makes for nice filler.

    Comment by John Armstrong | August 21, 2007 | Reply


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 366 other followers

%d bloggers like this: