Sometimes you hear people say that there's no point in trying to put a
certain feature into a program, because it's NP-complete.  Or maybe
they said it was equivalent to the halting problem.  Wait, aren't
those the same thing?

I'll take you through a quick tour of what it means to be undecidable,
NP-complete, and intractible, and what the differences are.  I'll
discuss the implications for practical problems like array bounds
checking.  I'll demonstrate the halting theorem, which says that there
are some things that just can't be computed, and Rice's theorem which
says that there are hardly any things that *can* be computed.  I'll
talk about hashing and encryption algorithms, including how to
generate unbreakable codes, how to prove that you know a secret
without revealing what it is, and how to flip a coin over the
telephone.