4 ms·
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 "practica
by ihodes 16y ago
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.
- amichail 16y agoComplexity theory seems only interested in algorithms that shed light on complexity classes. What has complexity theory done recently that is of practical importance?
- pmb 16y agoHow recently? Complexity theory seems to lead practice by around a decade...
- ihodes 16y agoA 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.
- jules 16y agoThat'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.
- yters 16y agoIt 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.
- nochiel 16y ago"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.
- dnautics 16y agothen 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."
- nochiel 16y agoTo 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.