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