News for hackers. Stuff that matters.
Re:Is Complexity Theory On The Brink? by ihodes on Thursday November 25, 2010 @02:41PM (#1940878)
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.
Re:Is Complexity Theory On The Brink? by jules on Thursday November 25, 2010 @08:38PM (#1941404)
That's not what complexity theorists work on. You could put any algorithm under the label complexity theory, but that's not what complexity theorists do.
Re:Is Complexity Theory On The Brink? by shadowfox on Thursday November 25, 2010 @11:27PM (#1941633)
So what do they work on?
Re:Is Complexity Theory On The Brink? by jules on Friday November 26, 2010 @01:31PM (#1942928)
Proving lower bounds on complexity and inventing algorithms that have theoretically better complexity but are most times useless in practice (for example the O(n^2.376) algorithm for matrix multiplication).