| 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 |