Elmo's World NP-complete problem (2006)

There's also a video of the associated talk here:

https://youtu.be/BJBnR5Sn-sc