Scott Aaronson and Lance Fortnow discuss What should physicists know about computational complexity?
I’m thinking that this deserves a rejoiner, “What should a computer scientist know about computational complexity?” I mean, how silly have these computer scientists been…they’ve been studying classical computers for all these years, when it is totally obvious (at least to a physicist like me) that they should have been studying quantum computers. 😉
This reminds me of my favorite way to distinguish between a computer scientist and a physicist at quantum computing conference. Physicists are the ones who think that NP stands for “not polynomial” and computer scientists are the ones who think that a Hamiltonian is some sort of sandwich.