Next | You can't get there from here | 3 |
In the description, I said
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.
I overreached here
I don't have time for the stuff in purple.
But this is the last talk of the conference
So perhaps I can run over
Next | Copyright © 2005 M. J. Dominus |