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

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.



Diamond Sponsors

Computer Associates International Inc., (CA)
Hewlett Packard
SpikeSource
Sun Microsystems

Platinum Sponsors

Novell, Inc.

Gold Sponsors

ActiveState
IBM
Ticketmaster

Silver Sponsors

ActiveGrid
Alfresco
Black Duck Software
CollabNet
Covalent Technologies
Google
GroundWork Open Source Solutions
Intel Corporation
Mergere, Inc.
Microsoft
Oracle
Palamida
SourceLabs
SugarCRM
Yahoo! Inc.
Zend Technologies, Inc.

Media Sponsors

boing boing
C/C++ Users Journal
DevtownStation News
Digital ID World
Enterprise Open Source Journal
Free Software Magazine
InsideMac Radio
Integration Developer News
Linux Journal
LinuxQuestions.org
Open Enterprise Trends
Queue
SDForum
Software Association of Oregon
Version Tracker
Wi-Fi Technology Forum
Women's Technology Cluster
WorldWIT

In-Kind Sponsors

Dell Inc.
Gibson
Griffin Technology
Harman Multimedia
Smugmug

Sponsors

OSCON 2005 Sponsor Opportunities — Email us at

Download the OSCON 05 Sponsor/Exhibitor Prospectus

OSCON 2005 Media Sponsor Opportunities — Call Margi Levin at 707-827-7184 or email at

Press and Media

For media-related inquiries, contact Suzanne Axtell at

Conference News

Want to receive conference news? Sign up for our email newsletter.

O'Reilly Home | Privacy Policy

© 2005, O'Reilly Media, Inc.