Okay, so those of you who know me know I love Fermi’s Paradox: “Where are they?” (And by “they” I mean extraterristrials, not some other they, like, physics and literature majors. I guess I’m more attuned to noticing that later odd specimen, but you’d be amazed at how popular that combination is.) One variant of the answer to Fermi’s Paradox is simply that the E.T.s are so advanced that they don’t really give a poop about us. Today I was pondering what could possibly make an E.T. think that we are so boring, so ordinary, that we were like specks of nothing in their eyes. And I thought, well maybe there is a computer science meets physics answer to this question!
A few years ago, we had this beautiful complexity class, BPP, of stuff that our ordinary computers could handle. Today we speculate that there is a slightly large complexity class which “ordinary” (and by ordinary I mean super challenging today, but possibly simple in the future) computers can handle: BQP. Now, suppose that this continues. As we probe deeper into the laws of physics we discover that we gain more and more computational power. We could even speculate that, there is a point where our physical laws allow us to solve NP-complete problems effeciently (that popping sound you just heard was Scott’s head.) As Lance and Scott has so beautifully pointed out, the consequences of this would be a reduction of large chunks of our culture to tractable problems. So if it were indeed true that physical allows for the efficient solution to NP-complete problems, then a society like ours, with our piddly classical computers and even our piddly future quantum computers, and our silly little things like the plays of Shakespeare are pretty boring objects. Large cunks of our society become nothing more than something which can be achieved on an alien laptop computer. Why bother visiting the Earth when not much interesting is occuring there which cannot be made a tractable problem on your computer.
Now of course, we know that NP is just one of a tower of higher and higher complexity classes (I would called it a zoo, but then I’d have to believe that a flood was near and that soon some some brave complexity theorist (who has a severe drinking problem) would have to pack up all the complexity classes, and their complements, into an ark in order to survive a flood which whipes out all other complexity theorists.) So even these luckily aliens who have access to a NP-complete solving computer and who therefore totally ignore us, might have their own Fermi Paradox? Are their levels of aliens all ignoring their lesser beings because of the weakness of the complexity classes their computers can efficiently solve?