In March 2012 Swedish TV recorded a popular science lecture of mine. It is now online.

I am an eager public speaker and have several crowd-pleasing talks that I can take off the shelf, say about how Google works. In March, I had the opportunity to record a lecture for Swedish TV’s educational channel Utbildningsradion. That audience is as “general” as it gets, so I wanted it to be broad and accessible. Something everybody immediately relates to. Something concrete and tangible.

What better choice than separation results for nonderministic polynomial-time computation? That’s right! In a fit of misguided ambition I decided to make a 20 minutes talks about honest-to-Karp theory of computation. P versus NP. Also, I did it in my fourth language: Swedish.

Here it is:

• Utopier i Science Fiction och Datavetenskap

I haven’t had the guts to watch it yet, maybe I never will. But as far as I remember, it came out well.

Some comments:

1. P and NP are the worst complexity class names ever invented, maybe the worst named concepts in all of science. I found it much easier to talk about Impagliazzo’s five worlds and focus on the dichotomy between Cryptomania and Algorithmica. These are meaty, sexy, fuzzy concepts rich with association and meaning. This is what we should talk about to the public. P and NP are just very cold, different, specific, nerdy instantiations of the same basic question.
2. Puzzles are good when explaining algorithms and their absence. I have a bunch of these talks, using paper folding, sudoku, or (as in this case) tiling puzzles. It gives you something tangible in a talk, and when you talk about something as abstract as computational complexity, you need all the tangibility you can get.
3. Science Fiction is our friend. I used various tropes from SF to ground the talk in a shared cultural space, and as an underlying theme. Here: the existence of hard artificial intelligence and the Singularity!. (I always say Singularity! in a booming voice. Hence the italics and exclamation point.)
4. The Singularity focus (sorry, Singularity! focus) was largely inspired by some transhumanistic alarmism on the blogs of Chalmers maths professor Olle Häggström (Okunnigt om artificiell intelligens och mänsklighetens framtid) and fantasy author R. Scott Bakker (The Posthuman Paradox). For some reason, the Singularity! exerts a strange attraction (ha!) on brilliant people like Olle and Scott. I simply can’t get myself worked up about it, and assume it’s simply the result of nonalgorithmic thinking that assails people who work in formal, possibly even quantitative, but nonalgorithmic settings. (Scott is a philosopher, Olle a statistician.) Alternatively, they could be right and I could be wrong. Still, it’s certainly fun to think about, and a great conduit for evangelising about algorithms to the public. The point of the talk is that the Singularity! is morally equivalent to P = NP. I think I manage to convey this point pretty well, given the constraints of the setting. In some sense, this is the maximally ambitious core of the talk. Neither Olle or Scott will be convinced by the argument, but the production values sure outshine their puny blog entries! Proof by intimidation.
5. I think I made the rhetorically correct decision of leaving the talk by moving the dystopias down to Earth in the end, with a bit of “algorithms are everywhere” internet evangelism.

In summary, the Singularity! is far. But then, the time-travelling nanobots paid me to say that, promising me a simulated eternity filled with cybervixens and Nutella.

Edit to add: I have been informed that I shouldn’t say “NP-hårt” in Swedish, but “NP-svårt.” Thanks, these things are beyond my linguistic intuition.

Related: Views of Impagliazzo’s Five Worlds.