Complexity classes

I just found this excellent explanation of complexity classes P, NP and more, explaining how it works, what it means, and the significance of it all. It's by Scott Aaronson, a theoretical computer scientist at the University of Waterloo. If you thought my last blog post on this subject was pointless (if I'm talking to you, you already know it), read this: it's at least some really cool-looking theoretical computer science and math. As far as I can tell, all it really assumes is knowledge of Big-O notation, which most of my readers probably already have (if not, see Wikipedia and the old blog post of mine linked above). Here's an indecipherable chunk from the lecture that will make perfect sense when you're done reading it:

Likewise, it's not hard to prove that if NP=coNP, then the entire polynomial hierarchy collapses down to NP (or in other words, to coNP). If Σ2P=Π2P, then the entire polynomial hierarchy collapses down to Σ2P, and so on. If you think about it, this gives us a whole infinite sequence of generalizations of the P≠NP conjecture, each one "harder" to prove than the last. Why do we care about these generalizations? Because often, we're trying to study conjecture BLAH, and we can't prove that BLAH is true, and we can't even prove that if BLAH were false then P would equal NP. But -- and here's the punchline -- we can prove that if BLAH were false, then the polynomial hierarchy would collapse to the second or the third level. And this gives us some sort of evidence that BLAH is true.

Welcome to complexity theory!

By the way, you may have noticed that this blog post is a lot shorter and has a lot more links and quotes than most of my past blog posts. Well, in one of my favorite blogs, Language Log, they were discussing French blogs and said,

At least, the half-dozen posts [on some stupid French philosopher's blog] that I've read are all plain-text essays, between 1,000 and 1,500 words each, with no hyperlinks, no quotations, no tables, no pictures. Even when he starts a post with a reference to someone else's writing, he doesn't link to it, and he doesn't even quote it, he just assumes that his readers will have read it and will know what he's talking about. Or maybe he assumes that they won't have read it, but will form an adequate opinion of its content from his discussion, I don't know.

Look, it's a supercomputer taken with
a wide-angle lens!

I can't emphasize this enough, so I'll put it in <em> tags: I am not a French philosopher!. For your further enjoyment, I have included a superfluous picture to the right. Have fun reading a real blog!