HTTP/1.1 301 Moved Permanently Date: Fri, 16 Jan 2026 13:16:57 GMT Server: Apache/2.4.41 (Ubuntu) Location: https://perl.plover.com/yak/Elmo/ Content-Length: 323 Content-Type: text/html; charset=iso-8859-1 HTTP/1.1 200 OK Date: Fri, 16 Jan 2026 13:16:58 GMT Server: Apache/2.4.41 (Ubuntu) Last-Modified: Tue, 24 Jun 2025 14:39:48 GMT ETag: "88c-638524ce226f9-gzip" Accept-Ranges: bytes Vary: Accept-Encoding Content-Encoding: gzip Content-Length: 1169 Content-Type: text/html

My Favorite NP-Complete Problem

Length: 10 minutes

Description

NP-complete problems are the hardest problems whose solutions can be efficiently checked for correctness. An efficient method of solving any NP-complete problem would translate directly into efficient solutions for all of them.

Many famous and interesting problems are NP-complete, but this is not one of them! This is the problem of how to distribute “Elmo’s World” segments onto a series of video releases.

Nobody knows a good way to solve NP-complete problems. The Elmo’s World people were not able to solve their problem either.

This 10-minute talk was prepared for !!Con 2016.

Outline

As my talks have gotten better, the slides have become harder and harder to understand without the accompanying commentary. So I've written up notes that you can read instead.

• Detailed notes
• Unintelligible slides
• Video (courtesy of Confreaks
• Talk transcript (courtesy of Mirabai Knight
• Blog post on which this talk was based

---

Return to: Universe of Discourse main page | Perl Paraphernalia | Other Classes and Talks

mjd-perl-yak+@plover.com