Computational Complexity: theory and practice

I was just reading this months CACM and I just wanted to share the editorial with you.
It has a great explanation of the P vs. NP problem and its importance, and, for those that didn't already hear, the alleged proof that P != NP has been verified incorrect, so the problem is still open (and you can still get the 1 million $ for solving it!).
It also makes a great point about Computational Complexity being an important theoretical field, but that it isn't always that relevant and/or helpful in practical algorithms design, which is a point I completely agree with, for example Big-Oh-Notation sure is useful, but reality teaches us that those pesky constants that we can "just forget" are actually quite important. And, while we're at it, let's not forget about actual resource usage, like memory, when comparing algorithms.
Great quote from the article to conclude:

An old cliché asks what the difference is between theory and practice, and answers that "in theory, they are not that different, but in practice, they are quite different."

Posted by Luca Longinotti on 19 Nov 2010 at 15:39
Categories: CompSci Comments

blog comments powered by Disqus