Next You can't get there from here 3


        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.

Next Copyright © 2005 M. J. Dominus