Monday, October 22, 2012

Song of the Complexity Classes

I tweeted the audio of this song last week and here is the video. Recorded at Dagstuhl on October 18th. Written by Fred Green who also plays piano. Performed by David Barrington with Steve Fenner on chorus.

Fred gives apologies to Gilbert and Sullivan, the Complexity Zoo, and Tom Lehrer



Lyrics by Fred Green, copyright 2012

To the tune of "I Am the Very Model of a Modern Major General"

There's P and NP, BPP and ZPP and coNP,
And TC0 and AC0 and NC1 and ACC,
There's PSPACE, LOGSPACE, PPSPACE and ESPACE, EXPSPACE, IPP,
And LIN and L and Q and R, and E, EE and E-E-E.
There's SPARSE and TALLY, PL, P/Poly, NP/poly,
There's PromiseP and PromiseBPP and PromiseBQP,
There's FewP, UP, QP, UE, N-E-E, N-E-E-E,
And EXP and NEXP, FewEXP, and NE-EXP, and also Max-N-P.
  And EXP and NEXP, FewEXP, and NE-EXP, and also Max-N-P
  And EXP and NEXP, FewEXP, and NE-EXP, and also Max-N-P
  And EXP and NEXP, FewEXP, and NE-EXP, and also Max-N, Max-N-P.
There's Sigma_nP, Delta_nP, Theta_nP, Pi_nP,
We know BPP's in Sigma_2P intersection Pi_2P.
And NP to the NP to the NP to the NP
To the NP to the NP, that's the pol-y-nom-yal hierarchy!

There's #P, gapP, PP, coC=P and MidBitP,
And ModP, Mod_kP, Mod_kL, ParityP, MPC,
There's FNP, NPSV, NPMV, and SAC,
SAC0, SAC1, SZKn and SPP.
There's BQP and DQP and EQP and NQP,
And RQP and VQP and YQP and ZQP,
And BPQP, FBQP, ZBQP, QRG,
QAC0, QNC0, QNC1, Q-A-C-C.
   QAC0, QNC0, QNC1, Q-A-C-C
   QAC0, QNC0, QNC1, Q-A-C-C
   QAC0, QNC0, QNC1, Q-A-C, A-C-C
There's QSZK, QMA and QAM and QIP,
And IP, MIP, QMIP and also PCP,
And PPPad and PPcc, PSK and PQUERY,
And PP to the PP, PExp, PPA and PPP.

These complexity classes are
the ones that come to mind,
And there may be many others but they
haven't been defined.

10 comments:

  1. Pushing the limits of geekery.

    ReplyDelete
  2. Yep, this isn't going to do much to remedy the stereotype of computer scientists as autistic taxonomists.

    I propose a new dichotomy. We'll call a problem BQOPTZX3 if it can be solved in less than O(n^(3+log(n))) time, and we'll call it SEMI-NON-BQOPTZX3-DUAL if it can't. Now open the floodgate of papers-- publish or perish, people!

    ReplyDelete
  3. Fun; I'll have to work on this song...

    ReplyDelete
  4. Thank you to have recorded a part of this music (and GCT) evening!
    NP

    ReplyDelete
  5. Anonymous 1: Yep, this isn't going to do much to remedy the stereotype of computer scientists as autistic taxonomists.

    That's a typo. You meant "artistic"

    ReplyDelete
  6. I started doing exactly this once, but you actually saw it through. Splendid!

    ReplyDelete
  7. Yep, this isn't going to do much to remedy the stereotype of computer scientists as autistic taxonomists.

    It's ironic that the "autistic taxonomists" are the ones who get to say to you: loosen up!

    ReplyDelete
  8. Rebecca black would be really mad at these guys ..

    ReplyDelete
  9. This song is Geek-Complete :)

    ReplyDelete
  10. Today I learned the PH collapses to the sixth level :P

    ReplyDelete