A simple Google search brings up a multitude of papers and book on the subject of the practical applications of complexity theory, so I'll spare you a list. Wik

A simple Google search brings up a multitude of papers and book on the subject of the practical applications of complexity theory, so I'll spare you a list. Wikipedia also has some nice example. RTFM, but I mean it in the nicest way. But, for instance, I recently ran into some complexity theory when exploring some of these topics, which are quite practical: • implementing a parser-generator • lambda calculus reductions (for a lisp-y interpreter) • encryption/security (you don't want there to be a simple function to crack your crypto, right?) It's totally useful, and totally relevant. And it's a lot of fun if you can get past the initial 90º learning curve.