Complexity Theory: Now a Path to Enlightenment

I’ve been insanely busy lately, which means I have a gigantic backlog of stuff that I meant to link to, but didn’t.

Scott Aaronson has a knack for taking certain interesting but not obviously revolutionary inspiring concepts in complexity theory and in good Russian-formalist fashion, making them strange. Here are some examples:

  • The Fable of the Chessmaster suggests that a perfect chess master could demonstrate their mastery to a high degree of certainty without revealing their strategies. Scott goes on to suggest that we can think of complexity theory as “mathematical theology” :-)
  • Logicians on safari connects complexity to super-intelligent aliens, the Riemann hypothesis to your car trunk, and that the fact that your computer crashes once a second is no excuse for not finishing your work.
  • More tender nuggets points out, among other things, that if babies can learn languages by example alone, they can also learn to break RSA.