Outreach

It occurs to me that the computer science community could do more to get its message across to young people, to encourage them to study. With this in mind, I have composed a song in the popular style known as "rap" designed to entertain but also to educate on some key CS concepts. I like to call it...

Smash the polynomial hierarchy!

I got the P! I got the NP!
Yeah, you know me!
I got coNP! I got BPP!
Got them all, don't you see...

Give me space! Give me logspace
Gonna take my place, gonna play my ace,
My AC0, gonna be a hero
People think I'm so bizarre, see
Gonna smash the polynomial hierarchy!

My warring machine is a Turing machine,
Recoil in horror y'all when you see my oracle
And call for your momma, yeah, when you meet my automata
Don't get mean, and don't you get snarky
But I smashed the polynomial hierarchy

Take any 3SAT, I spit it right back
Word to my homies all, it's polynomial
Me always in P-time, committing no crime
I steal RSA like it was your car keys
'Cause I smashed the polynomial hierarchy

I got the P! It equals NP!
I ain't on PCP!
I got RPP, all of NPC!
Million bucks be comin' to me

Stephen Cook better rewrite the book
C, L and R S attend my classes
And Michael Sipser can start calling me sir
Chris Papadimitriou can worship at my feet, yo
...don't you be calling me Aho, I ain't no ho...
[repeat to fade]



It's a work in progress, but what do you expect for 30 minutes work?