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 
6 Comments »
Leave a Reply
RSS Feeds
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.
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.
Why do you use the British spelling of Travelling ? Just curious.
It looks better. “Traveling” is.. a bit thin.
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.
There are a lot of these papers out there that give much more background than is strictly needed. It makes for nice filler.