Is Complexity Theory On The Brink? | Hacker News Reader

Is Complexity Theory On The Brink?

rjlipton.wordpress.com

56 pointswglb13 comments

Do you think complexity theory gets more attention than it deserves given its impact on practical computing?

Though I'm no complexity theorist, I can assure you than complexity theory is one of the biggest math/CS fields that has everyday, practical impact on "practical computing."

If you use any sort of non-trivial algorithms handling a non-trivial amount of data, you damn well better be interested in the relationship between the runtime of the algorithm and the number of things you're asking it to handle (Big O).

If you're designing a novel algorithm (or at least, novel to you) you should at least have a passing familiarity with complexity classes. It's funny how often I hear about (or see first-hand) someone trying to figure out why their code won't always work only to have pointed out to them that their problem is NP-C.

Not only all of that, but complexity theory supplies all sorts of better algorithms—or, rather, methods to improve a general class of algorithms, I suppose—which can immediately or eventually be applied to your everyday problems.

Perhaps you don't need to deal with a lot of these problems on a daily basis, but chances are that some of the tools you use were built by people who worried about them.

It's a neat field, and I'm excited to see these advances.

Complexity theory seems only interested in algorithms that shed light on complexity classes.

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

How recently?

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

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.

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.

So what do they work on?

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).

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.

"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.

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."

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.

Here's an example of the kind of research illustrating the gap between the priorities of complexity theorists and those of people who just want efficient algorithms:

It's a hard problem to approximate the volume of a convex body in n-dimensional space, given a membership oracle. (An oracle is an O(1) function that tells if a point is in, or not in, the convex body.) Is it exponential time in the number of dimensions (e.g., requiring an exponential number of calls to the oracle)? This is a fundamental question, and turns out to be important in lots of applications.

The following 1991 paper:

http://www.stat.duke.edu/~scs/Courses/Stat376/Papers/Converg...

caused quite a stir in the field. It has 380 citations. It proved, without explicit construction, that there is a (randomized) approximation algorithm that is order n^23, with a huge, and unknown, leading constant. It was totally useless in applications, but totally exciting for complexity theorists.

Since then, people have been plugging away. The most recent result I can find is by Laszlo Lovasz, appeared in 2003, and shows an O(n^4) algorithm. It's also randomized, very complex, and let's just say that the constant has got to be huge also.

The problem for practitioners is, you never know when all that plugging away is going to produce a good algorithm that is easy enough to implement. It it happens, it can totally change the computational landscape.

The FFT is my favorite example; its discovery has revolutionized all sorts of computations.

Reply on news.ycombinator.com