I gave a popular science talk this morning about which computational world we live in. The main conceit was to couple the question about the existence of efficient algorithms for NP-hard problems to utopias in science fiction and the technological singularity. I think this worked out pretty well.

The talk was recorded by Swedish TV and will be broadcast somewhen during the Spring of 2012 on their education and facts channel Kunskapskanalen. Because of the potentially high impact I decided to apply a bit more spit and polish to the visual side of the talk. In particular, I made 5 posters to represent Impagliazzo’s five worlds of computation. These worlds provide a metaphor that I find more intellectually stimulating than the relatively stuffy formulation, “Is the complexity class P equal to the complexity class NP?”.

I think some of them came out well, even typographically. (Five points for guessing which typeface was used for Heuristica.) I hereby release them under the CC BY-SA 3.0 license; maybe somebody else can use them in a similar talk. The talk was in Swedish (or at least in whatever language I use to approximate Swedish); if an anglophone wants Kryptomanien changed to Cryptomania, or wants the PDFs, I’m happy to oblige.

Next up: mugs, mouse mats, lingerie, and a perfume series of five fragrances.

References

Five worlds of computation are from Russell Impagliazzo: A Personal View of Average-Case Complexity. Structure in Complexity Theory Conference 1995: 134-147. [online PS]

Image sources: The dice are by ed_g2s at Wikimedia Commons. HAL 9000 is by Cryteria at Wikimedia Commons.