Sorry for the long delay! I had to be in Washington D.C. this week, for reasons I’m not at liberty to disclose. (Yes, I’m serious, and no, it’s not as interesting as it sounds.) Oh: on my way back to Canada, for some strange reason they confiscated my Blistex. I guess airport security guards get chapped lips a lot.

As our world descends even further into war, terror, and Armageddon, I have an exciting complexity-theoretic announcement. Building on the Complexity Zoo, Greg Kuperberg has created a “Robozoologist”: an expert system for reasoning about complexity classes. What’s more, Greg is releasing some spinoffs of his project to the masses, including a JavaScript-powered inclusion graph, and an automatically-generated RoboZoo. I can still remember them frontier days of 2002, when I had to herd the BP operators with my two bare hands…

15 Responses to “CIA, NSA, FBI, DoD, SZK, RNC, QMA, BPE”

  1. Greg Kuperberg Says:

    Thanks a lot for the announcement! To adjust the hype just a little bit, the RoboZoo is not completely automatic. It starts with a data file created by wetware, which is then checked and compiled by software.

    Also, the only real reasoning that the robozoologist can do is to survey the literature. E.g., if you tell it that there is an oracle that separates NP from BQP [BBB+97], and that NP is in PSPACE, it will say: therefore there is an oracle that separates PSPACE from BQP, again citing [BBB+97]. It actually has no model for any complexity class, other than its relations to other classes. (But as Scott alludes, it does know about class operators.)

  2. Anonymous Says:


  3. Scott Says:

    I guess I’d make a crappy undercover agent…

  4. Andy D Says:

    Way to go, Greg!

    I’m seeing the big diagram with some old-school map design underlaid, with high seas and ‘here-be-dragons’ starting around double-exponential time.

  5. Dave Bacon Says:


  6. Anonymous Says:


  7. Anonymous Says:

    Hi Scott,

    It appears an old friend of yours started a weblog:

  8. Scott Says:

    Thanks for the link! I can’t wait for the English version; I should drop Mahmoud a note welcoming him to the blogosphere.

  9. Nagesh Adluru Says:

    There is English version for that link. Just click on the flag with stars on the top right below his picture.

  10. Scott Says:

    Oops, my mistake!

    In the Name of God, the Most Merciful, the Most Compassionate

    Oh Almighty God, please, we beg you to send us our Guardian- who You have promised us- soon and appoint us as His close companions.

    During the era that nobility was a prestige and living in a city was perfection, I was born in a poor family in a remote village of Garmsar-approximately 90 kilometer east of Tehran…

    I can’t wait to see what my new fellow blogger comes up with next!

  11. Scott Says:

    Incidentally, there’s a poll on Mahmoud’s website:

    Do you think that the US and Israeli intention and goal by attacking Lebanon is pulling the trigger for another word [sic] war?

    95% voted “no.”

  12. Anonymous Says:

    Only 57% says no now.

  13. Anonymous Says:

    Trivia question (I don’t know the answer): is he the first president with a weblog?

  14. ano Says:

    Scott… your friend just did an interview with 60 Minutes.
    Here’s the first part:

  15. Anonymous Says:

    Scott, your friend
    attacked my computer