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.