« The Week in Web Languages | Main | Breaking Engima (still) »

Interactivity Helps

Scott Aaronson (of the Complexity Zoo) has a nice post called "The Fable of the Chessmaster" that talks about what computational complexity means in real terms—layman's terms, if you like.

He hits the nail on the head in pointing out that interactivity greatly helps communication: if you can ask questions, you can pursue the information you most want to know. This goes equally well for algorithms that are trying to decide some question as it does for human beings talking, whether in a formal presentation or chatting about bills. Interactivity helps.

In the human case, you may not always know what information you want to know, but you can also ask questions to help discover it. I suspect that fact has a complexity-theory analogue, though I don't know what it is. I am but a poor programming-language designer...

Finally, while I agree implicitly with Aaronson that complexity is about much more than computers, I don't think he's made the case. A chess game is a computation, isn't it? Does complexity theory cover things other than computations? Are there any computations that we'd meaningfully want to do away from a computer? And if so, are they large enough in scale that asymptotic complexity is relevant?

Post a comment