3 ms·

This article betrays the author's misunderstanding of complexity theory. Complexity theory is about finding algorithms which provably optimize some notion of ef

by j2kun 12y ago

This article betrays the author's misunderstanding of complexity theory. Complexity theory is about finding algorithms which provably optimize some notion of efficiency. Any notion of efficiency. Complexity theory is not equivalent to using asymptotic notation to describe things. In particular, when you find an algorithm that has, say, O(n) worst-case runtime, then you know that the time-complexity of the problem you're trying to solve is O(n). It could be better, like O(log n), and the goal of complexity theory is to do better or prove you can't. You could also try to find the query complexity of a learning problem in terms of the accuracy desired, or the round complexity of a problem solved by MapReduce algorithms in terms of the number of processors and the size of the input. > How does the algorithm perform in concurrent computing? Clearly we’d prefer an algorithm that can scale over processors to one that can’t ... Certainly there is a way to put this all together in theory, but I don’t know those details. There are no details to know. Any time you have any parameter of any system which can grow (processors, input size, time, space, cache layers) you can describe anything depending on that parameter using asymptotic notation to get a rough estimate of its efficiency. This is not a question of complexity, just a question of how to express growth rates succinctly. Knowing how to reason about rough estimates is essential for engineers because they have to have some idea about why the thing they're building will conform to specifications at least in principle before devoting the resources to measuring it precisely. And to reiterate: none of this has anything to do with complexity theory except that in complexity theory we happen to use asymptotic notation very heavily. The author's problem is with mathematical language being used in the workplace.

tptacek 12y ago
Yes, that's a compelling point, but to be clear: he's saying that the asymptotic analysis is itself not useful to programmers. We don't even reach the question of whether the field of complexity theory is relevant to programmers.
- j2kun 12y ago
  Exactly. He's using the wrong words to describe his point, which is that he doesn't think this particular mathematical language is useful. To someone who is fluent in that language, he makes it clear that he doesn't know how to use the language effectively (to stretch it, at times it doesn't seem like he even understands the semantics). But indeed, how could any sort of language be useful unless you know how to use it effectively?

by j2kun 12y ago

tptacek 12y ago

Yes, that's a compelling point, but to be clear: he's saying that the asymptotic analysis is itself not useful to programmers. We don't even reach the question of whether the field of complexity theory is relevant to programmers.

j2kun 12y ago
Exactly. He's using the wrong words to describe his point, which is that he doesn't think this particular mathematical language is useful. To someone who is fluent in that language, he makes it clear that he doesn't know how to use the language effectively (to stretch it, at times it doesn't seem like he even understands the semantics). But indeed, how could any sort of language be useful unless you know how to use it effectively?