Over at Shtetl-Optimized, Scott goes a little ballistic on criticism he’s received over the wording of his and Umesh Vazirani’s letters to the Economist. (As a side note, it is kind of sad to see such a poorly written article in the Economist: I know for a fact that an early Economist article on Shor’s algorithm drew a lot of great people into the field of quantum computing.) Part of Scott’s issue is with “physicists” insisting on rigor when they themselves are “the headmasters of handwaving.” So when Scott says
Today it is accepted that quantum computers could not solve NP-complete problems in a reasonable amount of time.
and he gets a lot of flack from physicists insisting that his statement might be interpreted as BQP not containing NP, he gets rather ticked off since those “headmasters of handwaving” themselves make all sorts of statements like this and don’t seem to mind. “Double standard!” shouts Da Optimizer!
Now one could take Scott’s rant and turn it into a great computer-science physics flamewar, but what fun would that be? And I’m a softy (or a Chinese restaurant placemat, depending on your perspective), so I’d like to take what Scott has said and turn it around. Therefore, let me declare the following Pontiffical edict:
Welcome to the headmasters of handwaving club, theoretical computer scientists! We’ve got a seat ready for you right here at our table, all full of delightful theorems and lemmas which you can eat….without having to give a proof of their validity. Our feasts our grand, our parties even wilder, and our nights filled with wonder and awe. Sure you may get a little indigestion, what with the unproven or even, dare I mention the word, wrong, theorems, tumbling around in your belly, but look at what you get in return! Did I mention the wild parties?
I guess in my mind, I actually think that computer science and physics have a lot more in common with each other than either side would ever dare admit. For example, researchers from both fields, it seems to me, can be placed (borrowing the terminology of physics only because of stuff in my past light-cone) neatly on a linear diagram from “experimentalist” to “theorist.” Just as “experimental computer scientists” complain to death about the lack of usefulness of the algorithms invented by “theoretical computer scientists”, “experimental physicists” spend vast hours complaining about the indigestability of the vast body of the “theoretical physics.” But every so often, in this tension, the theorist from both sides do something so remarkable and so practically important that the experimentalists get really excited and actually take the theory and put it to use. Similarly, theorists from both sides who don’t take heed of the experimental side of their field are, it seems to me, destined for obscurity. For example a theoretical physicist who ignores the fact that thier pet theory violates nearly every experiment ever performed, or a theoretical computer scientist who works with a model of computation so irrelevant to modern computation that no one notices (and no I don’t put the entire complexity zoo into this category: the reasons for studying the zoo go far beyond simply defining complexity classes so obscure as to be irrelevant…the beauty of the best complexity classes is exactly in their relevance to our real world computation questions.) both share a common destiny in the dustbin of irrelevant results.
So, rejoice, physicist and computer scientists! You masters of the twentieth century, makers of the grandest constructions in the world and in our minds, and find peace in fighting against your common rising enemy: those damn pesky biologists!