Xkcd: Travelling Salesman Problem | Hacker News Reader

Xkcd: Travelling Salesman Problem

xkcd.com

41 pointsbkrausz14 comments

So I looked through the last 10-15 or so of the xkcd comics, and maybe 3-4 of them were what I considered HN material (Feynman, this one, etc) and a bunch that were not (tripping band kids, punch buggy, tapping, etc). The appropriate ones (like this) have a lot of upvotes, the others don't. I'm happy to announce that the system is working, the good ones are rising and the bad ones are getting ignored.

Remember, commenting to complain about the bad ones makes them rise to the top of the front page!

"A webcomic of romance, sarcasm, math, and language."

Notice how only one of those is math. I think it is by design that only ~1/3 of them are HN material.

Don't get me wrong, lots of those other ones were funny, just not HN material. I'm a faithful subscriber to their RSS feed.

In the last 16 I saw 10 I would expect to be of interest to at least a handful of readers here:

The Drake Equation (funny math)

How it works (stereotypes & math)

Advanced Technology (von neumann machines)

Fuck Grapefruit (scatter plot about perception)

Nightmares (creative subconscious, what's not to love?)

Ultimate Game (D&D is not for me, but I think it fits the crowd)

Kilobyte

Morning (dead pixels)

Zombie Feynman

TSP

Before reading "O(1)" I thought it would be written "Priceless".

However I think that's the idea, but using programmers currency.

Shouldn't it be O(N)? I mean, the time taken to pack and send your products will still scale linearly with the number of customers, right?

You raise a good point, but O(1) is a much better punch line.

It's definitely more stark, but O(N) would have gotten a chuckle from the intended audience and a nod to Randall for getting his complexity right.

But I'm just advocating for the devil...

Well, just to argue against my original point, the scaling of the travelling salesman problem usually applies to the time taken to figure out the optimal route, not the time taken to actually traverse it, which is O(N). If you're just looking at the route-planning stage, then the "sod it, I'll just sell on eBay" algorithm is indeed O(1).

This proves without a doubt that selling online solves np-hard complexity. And you don't even need a Turing Machine.

The reviews on ebay are turing complete. You might think people are giving over the top reviews with their "A+++++++++", but that's just unary notation.

Syntax error...you have an odd number of pluses :P

One of best xkcd comics in recent memory. Come Monday, I'll be printing it out and taping it up on my monitor.

I didn't gain any insights from that cartoon.

Reply on news.ycombinator.com