My Favorite NP-Complete Problem

Length: 10 minutes


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.


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.

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