My friends are not computer science, but I’ve talked about NP-Completeness enough for them to know to zone out when the phrase comes up. I find the topic extremely fascinating, as at some level I feel like Algorithms courses are where math best meets computer science. Well, outside of scientific computing. Or graphics. Regardless, the two disciplines meet here.

Reading Coding Horror, I found this gem:

NP-complete problems are like hardcore pornography. Nobody can define what makes a problem NP-complete, exactly, but you’ll know it when you see it. Just this once, I’ll refrain from my usual practice of inserting images to illustrate my point.

Hilarious. The rest of the article is good, too.

Recently, my friends and I were at my school’s Divali festival. It was very crowded, and it was tough to find a set of three consecutive chairs at any table for us to all sit at. I recognized this immediately as bin-packing, an NP-hard problem. Basically, the tables are bins, and you have groups of various sizes (some people came alone, some in pairs, etc.) that you want to fit into these bins wasting as little space as possible / using as few tables as possible. Another example of this problem might be going to the movie theatre with your friends / family. My friends got bored pretty quickly when I brought this up.