The Blog of Scott Aaronson If you take nothing else from this blog: quantum computers won't solve hard problems instantly by just trying all solutions in parallel.
Also, next pandemic, let's approve the vaccines faster!
A little-known discipline of science called computational intractability studies the boundaries of our understanding – not questions of the philosophical realm (Is there a god? An afterlife?) but of the everyday computational realm.
So says the Boston Globe, in an article that’s finally appeared, after it apparently kept getting bumped for personal health stories (I guess NP-completeness still doesn’t move papers like cancer). I’m gratified: in this time of economic crisis, the world urgently needs more articles about what humans still won’t be able to do in a billion years. (A colleague complained to me that computational intractability is not “little-known”; in fact, almost all computer scientists know what it is. I’m not sure if he was joking.)
Speaking of Public Understanding of Science: as you may have heard, much of the future of American science now hinges on whether the Senate, as it haggles over the $800B stimulus, decides to sprinkle a breadcrumb or two off the table for us. If there was ever a time to email your Senator’s office, and have a staff person check a box marked “constituent complaining about science funding” in your name, it’s probably this week. The APS has drafted a letter for you.
Today I continue a three-entry streak of praising things that are good. While visiting IAS to give a talk, I noticed on several of my friends’ desks heavily-bookmarked copies of the Princeton Companion to Mathematics: a 1000-page volume that’s sort of an encyclopedia of math, history of math, biographical dictionary of math, beginners’ guide to math, experts’ desk reference of math, philosophical treatise on math, cultural account of math, and defense of math rolled into one, written by about 130 topic specialists and edited by the Fields medalist, blogger, and master expositor Timothy Gowers.
The best way I can explain what the PCM is trying to do is this. Suppose that—like in the Hitchhiker’s Guide to the Galaxy—aliens are threatening to obliterate the earth along with all its life to make room for an interstellar highway. But while the aliens are unresponsive to pleas for mercy, an exemption might be granted if the humans can show that, over the last four millennia, such mathematical insights as they’ve managed to attain are a credit rather than an embarrassment to their species. To help decide the case, the aliens ask that humans send them an overview of all their most interesting mathematics, comprising no more than 1,000 of the humans’ pages. Crucially, this overview will not be read by the aliens’ great mathematicians—who have no time for such menial jobs—but by a regional highway administrator who did passably well in math class at Zorgamak Elementary School. So the more engaging and accessible the better.
I don’t know what our chances would be in such a situation, but I know that the PCM (suitably translated into the aliens’ language) is the book I’d want beamed into space to justify the continued existence of our species.
So what makes it good? Two things, mainly:
For some strange reason I still don’t understand, it’s written as if you were supposed to read it. Picture a stack of yellow books (), and imagine cornering the authors one by one and demanding they tell you what’s really going on, and the result might look something like this. Admittedly, there are plenty of topics I still didn’t understand after reading about them here—Calabi-Yau manifolds, K-theory, modular forms—but even there, I gained the useful information that these things are apparently hard for me even when someone’s trying to make them easy.
The book is cheerfully unapologetic about throwing in wavelets, error-correcting codes, the simplex algorithm, and the Ising model alongside the greatest hits of algebra, geometry, analysis, and topology—as if no one would think to do otherwise, as if the former were part of the mathematical canon all along (as indeed they could’ve been, but for historical accident). Nor does it dismay me that the book gives such a large role to theoretical computer science—with a 30-page chapter on complexity by Avi Wigderson and Oded Goldreich, as well as chapters on cryptography, numerical analysis, computability, and quantum computing (my tiny role was to help with the last). There are also essays on computer-assisted proofs, “experimental mathematics,” innumeracy, math and art, and the goals of mathematical research; a guide to mathematical software packages; “advice to a young mathematician”; and a timeline of mathematical events, from the first known use of a bone for counting through Shor’s factoring algorithm and the proofs of Wiles and Perelman.
But enough! I must now descend from Platonic heaven, reenter the illusory world of shadows, and finish my grant proposal … alright, maybe one more puff …
Follow
), and imagine cornering the authors one by one and demanding they tell you what’s really going on, and the result might look something like this. Admittedly, there are plenty of topics I still didn’t understand after reading about them here—Calabi-Yau manifolds, K-theory, modular forms—but even there, I gained the useful information that these things are apparently hard for me even when someone’s trying to make them easy.