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



ExpoVina 2010, HP 7.1

Went to ExpoVina again this year, awesome as always, great wines, great people and great company! ;)
The port wines at Amarela were incredible, and as usual it isn't only wine you get to taste there. Had to order the chocolate-pepper, yum!!! And the bread with the right olive oil... delightful!
Bindella also got all the good Italian dessert wines, and "Vigna Senza Nome" was even at a reduced price!

On another note, I went to watch "Harry Potter and The Deathly Hallows - Part 1" yesterday evening at the Abaton, which thankfully has extremely comfortable seats, as I alternated between moments of sleepiness (thankfully much fewer than in the 5th and 6th movies!), and moments of "Gaahh wtf eh?"... I admit to never having finished reading book 7, as it just sucked so much, and the film reflects that, completely random items quest, coupled with teenage angst, and let's add a few mythical artifacts just for fun, and don't get me started on the magic, that's probably my biggest gripe with the HP films: the magic effects just SUCK, it's always just random lights and explosions that do comparatively little damage (only cool explosion I saw was Hermione using Bombarda once, why don't you always use it, if you know it, wtf? And Voldemort's lightning spell towards the end). Basically I find the magic much too tame, I mean, if you can control energy and the elements, make it go Boom! more often... And the flying black clouds of Death Eeaterness, the LOLZ, I can't remember anything in the books that justifies that... Will have to wait till July 2011 for the second part, which I'll probably still watch in a masochistic attempt at completing the set. :)
In the end there thankfully is fan-fiction, much of which I find better than the original books, and there are other, much better fantasy series to keep one's self entertained, The Dresden Files, The Mistborn Trilogy, and the king, The Lord of the Rings.

Posted by Luca Longinotti on 19 Nov 2010 at 14:46
Categories: Longi Comments




(Page 1 of 1)