O'Reilly Open Source Convention - August 1-5, 2005

Session
You Can't Get There From Here
Mark-Jason Dominus, Chief Programmer, Plover Systems Co.

Track: Emerging Topics
Date: Friday, August 5th, 2005
Time: 11:35am - 12:20pm
Location: Portland 251
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?
Dominus takes you through a quick tour of what it means to be undecidable, NP-complete, and intractible, and what the differences are. He discusses the implications for practical problems like array bounds checking. He demonstrates 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. He talks 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.