NP-complete problem solved in constant time

By -
(For computer science geeks only). This xkcd cartoon is about a revolutionary constant-time solution to the famous Travelling Salesperson problem.

Comments

Post a Comment

Popular posts from this blog

Where is 56th and Wabasha? "Meet Me in the Morning" Dylan Mystery Solved

By -
Image
Short version The lyric is not "Fifty-sixth and Wabasha", it is actually "Fifty-six and Wabasha", referring to the intersection of old Minnesota Highway 56 and Wabasha Street in Saint Paul, Minnesota. If you listen, you can hear Dylan sing "fifty-six", rather than "fifty-sixth", particularly on the take that was released as the B-side to "Duquesne Whistle". Minnesota Highway 56 no longer intersects Wabasha Street, but from 1963 to 1974 it did intersect Wabasha Street, at what is now (in Feb. 2021) the intersection of George Street and Cesar Chavez Street in St. Paul, or possibly South Wabasha & Cesar Chavez.  Long Version "Meet Me in the Morning" is the first song on side two of Bob Dylan's celebrated 1975 album  Blood on the Tracks. In the opening lines of the song, according to the lyrics on Bob Dylan's official site (https://www.bobdylan.com/songs/meet-me-morning/), the narrator invites the listener to a rendez...
Read more

Random harlot generation table in AD&D Dungeon Master's Guide

By -
Image
GenCon Indy approaches, and so I'm not posting much. I hear D&D co-creator Gary Gygax will be at the convention this year. If I run into him, I want him to autograph one of the most ridiculous pieces of gaming weirdness ever to make it into a mainstream AD&D publication. I'm speaking, of course, about the infamous random prostitute generation table in the 1st Edition Dungeon Master's Guide . That book included a random encounter table for cities; "Harlot" is one of the entries. Here is the Harlot entry, reproduced in facsimile for your delectation: Sadly, subsequent editions of the Dungeon Master's Guide lack such useful prompts to the imagination. Dungeon Masters are now forced to improvise descriptions of harlots, should such be encountered by an adventuring party. Unless, of course, the Dungeon Master owns a copy of the 1st Edition DMG or is lucky enough to see this blog post. In the interest of fairness and gender equality, this table should be...
Read more

Snarking The Odyssey (with AD&D)

By -
Image
WARNING: Those of you who are accustomed to pithy political remarks here on Internal Monologue should brace yourselves for a major dose of gaming geekitude. Here's a link to one "Jamie R." who does a very snarky close reading of Homer's The Odyssey (HT: Mad Latinist via email). I've only read book 1, but it's pretty funny so far. An excerpt: Tell me, O muse, of that ingenious hero who travelled far and wide after he had sacked the famous town of Troy. Many cities did he visit, and many were the nations with whose manners and customs he was acquainted; moreover he suffered much by sea while trying to save his own life and bring his men safely home; but do what he might he could not save his men… Sooooo, he’s in charge, and everybody dies. Tell me, O muse, of that ingenious hero and his colossal failure. What? … for they perished through their own sheer folly in eating the cattle of the Sun-god Hyperion; so the god prevented them from ever rea...
Read more