Archive for April, 2006

An entry contained in a blog

Friday, April 7th, 2006

Time for a little pet peeve. I’ve gotten numerous emails that say something like, “In your last blog…” when what they mean is, “In your last blog entry…”

A blog is a collection of entries (or posts). The set of possible entries is only countably infinite, but the set of possible blogs has the cardinality of the continuum.

(In practice, the positivity of the cosmological constant does impose an upper bound of about 210^122 on the number of possible blogs. But that’s merely a contingent fact about our universe, and is not intrinsic to the notion of blog. Logically, there’s no reason for a blog ever to end — even though any particular entry, including this one, must.)

I’m mad as hell and I’m not gonna take it anymore

Sunday, April 2nd, 2006

What am I mad about? Oh, God.

I’m mad about Bush receiving Michael Crichton in the White House, to be reassured that climate change is a hoax even as the Northwest Passage opens up for the first time in a few million years. I’m mad about the Democrats’ failure to capitalize on the Enron scandal, and particularly the infamous “Grandma Millie” tapes (having just watched the film Enron: The Smartest Guys in the Room). I’m mad about Pius XII, the man who arm-twisted Germany’s 23 million Catholics into cooperating with the Nazis despite their initial opposition, being considered for sainthood (I’m in the middle of a book about it, Hitler’s Pope by John Cornwell). I’m mad about my own procrastination in writing a popular article for Scientific American about the limits of quantum computing. I’m mad about a public school system that condemns any math or science tracking as “elitist,” while the football and basketball programs aren’t similarly condemned. I’m mad about people who declare that “a proof of P!=NP would be worthless, since what if there were an algorithm for SAT that took 1.0000001n steps?,” as if no one had ever had such a perceptive insight in the 50-year history of complexity theory.

But, as for the “not gonna take it anymore” part, one does have to restrict one’s focus a bit. So recently I decided to concentrate my anger on overpriced journal subscriptions — and in particular, on the gouging of university libraries by companies like Kluwer and Elsevier. I’ve just written a three-page polemic about this issue (technically a book review), which is going to appear in SIGACT News, possibly with a rebuttal and counter-rebuttal. I’d be grateful for comments. Note that what I write about scientists’ “peculiar anger deficiency” applies to many other issues, global warming being one obvious example. There comes a time when it’s no longer enough to be correct: you also have to be angry!

Thanks to Bill Gasarch, both for commissioning the review and for suggesting the title of this post.

Note: My diatribe is also available in HTML and postscript.

The rumors are true

Saturday, April 1st, 2006

Yeah, alright. I, Scott Aaronson, have been arrested and have spent eight hours in the custody of the Waterloo police.

Since a lot of bogus information has been circulating about how this happened, let me give you my side of the story. It’s easiest to start with Gaurav Mukherjee, who’s currently an undergrad at IIT New Delhi. I assume most of you have heard of him by now (he’s been all over the blogosphere), but for those who haven’t: earlier this week Mukherjee announced a proof of the “physical independence” of P versus NP and related questions. In a manuscript that’s been circulating by email, he claims to exhibit laws of physics under which P equals NP (in the unrelativized setting), and different laws under which P doesn’t equal NP. Indeed, he even claims to give laws under which P=NP can exist in a quantum superposition of truth and falsehood.

When Gaurav sent me the manuscript on Wednesday, I immediately wrote it off as crackpot nonsense. So when I visited Perimeter Institute yesterday afternoon, I was astonished to find it was all anyone was talking about! I tried in vain to argue with the physicists: “Look, you don’t get it. P versus NP is a mathematical question. By definition, its truth or falsehood can’t depend on any assumptions about physics.”

“Have you even read the paper?” the physicists would shoot back. “That kind of statement only makes sense in a pre-Mukherjee ontology. You might as well say after Einstein’s paper that the rate of time can’t possibly depend on how fast you’re moving!”

“No, that’s a shitty analogy!” I’d respond, getting more and more agitated as the afternoon wore on.

At 9PM or so, a bunch of us decided to hit Jane Bond, a popular bar in Waterloo, to argue about it some more. That’s where things took a turn for the worse. I’ve never held my alcohol well, but the physicists were all ordering three or four beers apiece, so I did the same. By midnight, I’d gotten into an especially ugly argument with a certain postdoc who will remain anonymous. “You complexity theorists, you’re all the same,” he drawled. “Prove this, bound that, this makes no sense, this can’t possibly influence that. Buncha stuck-up pussies.”

The physicists all laughed, and that’s when I lost it.

“You idiot!” I screamed. “You doofus! You ignorant farmer!”

“What did you call me?” the postdoc said, pushing my shoulder so hard I almost fell off my chair.

“An ignorant farmer,” I said, socking him in the jaw as hard as I could.

We both got up. I noticed that the postdoc’s jaw was bleeding. The other Perimeter guys gathered around us — quantum information theorists on one side, cosmologists and quantum gravity theorists on the other. The postdoc and I traded blows for a minute or two until the cops showed up. When they asked who started it, everyone pointed to me, and as a result, I was the only one they arrested! Fortunately, the cops said they wouldn’t charge me with anything, but they did keep me at the station until I sobered up.

I had plenty of time there to think things over. What if Mukherjee is right? I thought. What if the very formulation of Turing machines, P versus NP, and so on depends on presuppositions that I’ve never seriously thought through? There was one particular point in Mukherjee’s paper — the construction of an ontology where polynomial time means the same as exponential time — that I hadn’t understood till then, but that I finally got at 4AM or so. Staring at the walls of the station, the lone officer pacing back and forth, my handcuffs, etc. I could feel my previous worldview crumbling all around me.

By now — Saturday morning — Mukherjee’s paper has changed how I think about almost everything. This might seem like a stretch, but it’s even made me more sanguine about the George W. Bush presidency. Look, if whether P=NP can depend so strongly on our beliefs and assumptions, then why not whether the universe is 6,000 or 14 billion years old, or whether a missile defense system will or won’t work? The bottom line is that facts, logic, and “objective reality” (whatever that means) aren’t nearly as important as I thought they were. If enough people want something to be true, it becomes true. I guess I’ll keep writing this blog, but from now on it’s never going to be the same.