Links for 2012-03-16

We prove NP-hardness results for five of Nintendo's largest video game franchises: Mario, Donkey Kong, Legend of Zelda, Metroid, and Pokemon. Our results apply to Super Mario Bros. 1, 3, Lost Levels, and Super Mario World; Donkey Kong Country 1-3; all Legend of Zelda games except Zelda II: The Adventure of Link; all Metroid games; and all Pokemon role-playing games. For Mario and Donkey Kong, we show NP-completeness. In addition, we observe that several games in the Zelda series are PSPACE-complete.

To paraphrase E.B. White, the perfect sentence is one from which nothing can be added or removed. Every word plays its part. In my more giddy moments I think that a simple comic strip featuring Calvin, a preternaturally bright six year-old, and Hobbes, his imaginary tiger friend, features some of the most lucid sentences committed to print. And when I sober up, I usually think exactly the same. Bill Watterson's Calvin and Hobbes ran between 1985 and 1995. His comic strip managed to infuse wondering (and wandering) on a cosmic scale into an ageless world of lazy Sunday afternoons, snow goons, and harassed babysitters. I'm not saying that you should take moral and philosophical guidance from the inventor of Calvinball (a game that runs on chaos theory), but you could do much worse. So here, in no particular order, is a selection of quotes that nail everything from the meaning of life to special underwear. Enjoy.

Need a sentence for your latest article? Write one here! Just select a word or phrase from each drop-down list and click "Write It." Don't like the sentence? You can use the same words in a different sentence by clicking "Edit It." (Click "Edit It" repeatedly to see several options!) Or to write something completely new, you can change one or more of the words you've selected and click "Write It" again. Have fun!

Since its digits are random, and they never end, in principle any sequence you could ever imagine should show up in pi eventually. In fact there is a nifty website here that will let you search for arbitrary strings (using a 5-bit format) in first 4 billion digits, for example "alemi" seems to show up at around digit 3149096356. So in principle, I could send you just an index, and a length, and you could compute the resulting file.