News for hackers. Stuff that matters.
Re:Is Complexity Theory On The Brink? by amichail on Thursday November 25, 2010 @02:28PM (#1940855)
Complexity theory seems only interested in algorithms that shed light on complexity classes.

What has complexity theory done recently that is of practical importance?

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).
Re:Is Complexity Theory On The Brink? by nochiel on Thursday November 25, 2010 @04:43PM (#1941076)
"What has complexity theory done recently that is of practical importance?"

It is probably worth noting that "practical importance" is probably the least useful measure of the value of pure research. In fact, historically, applications emerge from high level mathematics which was began with no practical applications initially in mind.

Re:Is Complexity Theory On The Brink? by dnautics on Friday November 26, 2010 @02:45AM (#1941846)
then it's not "on the brink". It's true that stuff like the fourier transform led the information revolution, and that it was discovered in 1700, but it was not "on the brink" in the 1700s.

It's not "on the brink" until I can explain how it functions to a lay person, in one sentence to explain what it does and in one sentence why they should care. E.G: Fourier transform:

"It's something which takes a complicated wave and finds out what simple waves add up to the complicated wave. This is useful, for example, because sounds are complicated waves, if you know what simple waves there are, you can do things like autotuning."

Re:Is Complexity Theory On The Brink? by nochiel on Thursday December 02, 2010 @11:21AM (#1962525)
To be fair, in the article he qualifies his title by saying that, "I think that complexity theory is on the verge of major breakthroughs of all kinds...potentially major advances across the entire spectrum of theory.(emphasis mine throughout)"

Clearly you have a rather unique idea of what "on the brink" might mean, namely that the field is on the verge of providing breakthroughs that have concrete applications. That might be a rather limiting point of view that somewhat cheapens the value of the article.

Re:Is Complexity Theory On The Brink? by pmb on Thursday November 25, 2010 @02:38PM (#1940873)
How recently?

Complexity theory seems to lead practice by around a decade...

Re:Is Complexity Theory On The Brink? by yters on Thursday November 25, 2010 @04:06PM (#1941002)
It has shown most problems of interest to us can't be adequately solved with computers. They can give us some suboptimal solutions, which can be useful, but do not live up to the expectations for the IT field.

See the No Free Lunch Theorem.