December days: P vs. NP

On our date a couple of weeks ago, I found myself explaining to ghoti the basics of why P vs. NP is an interesting question. (Clearly, we have the best romantic conversations.) I'd like to explain this at a bit more length and to more people. You'll have to care at least a little bit about maths to find this interesting, but I hope I've managed to explain it clearly enough that it doesn't require any specialist knowledge. Note that I'm not actually a complexity researcher, just an interested person with some relevant background.

( the essence of hard problems )

This post is part of my December days series. Please prompt me!