Length: 60 minutes
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.
Return to: Universe of Discourse main page | Perl Paraphernalia | Other Classes and Talks
mjd-perl-yak+@plover.com