- There so much Drama in the PhD PROS: Hilarious and mostly on topic. CONS: Offensive to some. Maybe even to most. Maybe even to me.
-
Mathematics Paradise
PROS: Hilarious and edgy without being offensive.
CONS: Actually a math song.
SUGGESTION: Could someone rewrite this for our purposes?
-
~
Monday, June 18, 2007
Complexity Theory Theme Song options
Scott Aaronson
asks for a Complexity Theory Theme song
and composed one, with help, called Down with SPP.
I have not composed any, but I offer two other options.
Subscribe to:
Post Comments (Atom)
My first thought was to base a song on "A Touch of Class", which turns out to be the name of a former German techno group. They had one smash hit in 2000, "Around the World", whose lyrics are here.
ReplyDeleteA couple of lines show some promise, e.g. to make "Inside an empty brain my inspiration flows", and maybe we can play on relativized "worlds", but it's not great. And I can't parse the "melody". So maybe start with something else. I have some track record here, e.g. "Bugs", but with lots on my plate I'm happy to promote this as a community pitch-in effort...
MC Plus Plus seems to believe that NP=PSPACE but he backs up his claims only with obscence boasting.
ReplyDelete"... I'm PSPACE-complete but I'll reduce you to 3-SAT. My crew is so hard that we roll in NP..."
"I'll beat your ass until it's colored like a red-black tree"
I'd like to believe that this sort of thing wouldn't get past the FOCS/STOC reviewers....
Obscene boasting. STOC/FOCS reviewers. Sounds a good match to me.
ReplyDelete#2, Monzy is the composer of that song. MC Plus Plus is the guy he's dissing.
ReplyDeleteNo, he doesn't believe NP=PSPACE. See, he's PSPACE complete, but he will reduce YOU to 3SAT. So if NP != PSPACE, he is harder than you are, which is the claim he is making.
ReplyDeleteTrue, he is so hard that he rolls in NP, which just means that as a PSPACE-complete rapper, he is able to roll in NP, which is YOUR hood, as you can be reduced to 3-SAT.
You can't beat Guy Steele's classic, The Telnet Song. Just as N Green Bottles has complexity O(N), and The N Days of Christmas has complexity O(N^2), The Telnet Song has complexity O(2^N).
ReplyDeleteCHALLENGE FOR CCC 2008:
ReplyDeleteCome up with a meaningful definition for a problem to "roll" in another (potetially lower) complexity class.
Extra points if you present a PSPACE complete problem that rolls in NP, super-extra points if you can present two different PSPACE complete problems, one of which rolls in NP and another that (modulo plausible hypotheses) does not roll in NP.
Maybe someone could adapt
ReplyDeleteThe 12 days of research to be complexity-specific.
Commenter #7, given a class D, let us define Pre(D) to be the intersection of all classes C, themselves closed under logspace many-one reductions, such that D is contained in the poly-bounded existential closure of C. [The last clause means that for every language A \in D, there are a language R \in C and a polynomial p such that for all strings x, x \in A iff (\exists y: |y| = p(|x|))xy \in R.]
ReplyDeleteNow define a language A to "roll in" a class D if the downward closure of A under Pre(D)-many-one reductions equals P^A.
Then your super-extra-points conditions are met unconditionally: Pre(NP) = L (logspace). QBF is complete for PSPACE under logspace many-one reductions, so QBF rolls in NP. Osamu Watanabe, in a 1987 paper in Theoretical Computer Science, constructed a language B in PSPACE that is complete under polynomial-time Turing reductions, but not under logspace many-one reductions, so B does not roll in NP.
Sorry, your challenge as-worded was met by a CCC regular 20 years ago :-). Allender et al., "Power from Random Strings" give more-natural examples of such languages B. It may seem surprising that P-Turing and L-many-one reductions are known to differ on PSPACE, but the point is that if P = L then P != PSPACE, and feasible many-one and Turing reductions can be made to differ pretty freely in regions known to lie outside of P.
Here's my attempt at a theme song. I apologize for the length of the comment, but Bill suggested I post this, so I'm covered. :-)
ReplyDeleteMusic, lyrics and video for 'White & Nerdy' are currently streaming at www.myspace.com/weirdal.
I JUST DO THEORY
(lyrics by Aaron Sterling 19 Jun 07, inspired by Weird Al Yankovic’s ‘White & Nerdy’. Original music and words by Chamillionaire, ‘Riding’.)
(If you have the bad taste to show this to anyone else, be sure to tell them it was my fault, not yours. And if someone offers you $20 to stop spamming them with it, send me the money.)
They see me proving my theorem.
I know they’re all thinking I just do theory.
Think I just do theory.
Think I just do theory.
Can’t you see I just do theory?
Look at me, I just do theory!
I wanna code with the hackers
But so far they think I just do theory.
Think I just do theory.
I just do theory.
Really, truly, just do theory.
I wrote a program that solved TSP
Superduperpolynomially.
Ain’t no such thing as lunch for free
When you’re digesting P-NP.
Unnatural proofs are my favorite vice
When I dream of solver’s paradise.
But my poor construction just won’t suffice,
Even when I add Karp-Lipton advice.
Yo! There’s more to life than just systems!
I may not get the joint jumping
But my lemmas can do some pumping.
God knows I’d better think of something
To stop the NSF from dumping
My new proposal. Is it practical? Well, gee,
Vertex cover is tactical, see?
Shows the battalion just where to pee
With suboptimal propinquity.
Don’t know how to start an IDE
But I’m a wizard at that MA-E,
Playing games with PPAD.
My languages are always acceptable.
My LaTex skills? They are impeccable.
My proofs are probabilistically checkable.
But what I compile just isn’t respectable.
You see, I just do theory.
They’re on RA, while I’m teaching.
That’s how they know that I just do theory.
Know I just do theory
Know I just do theory
I admit it, I just do theory.
Look at me, I just do theory.
I’d like to code with the hackers
Although it’s apparent I just do theory
Yes, I just do theory
Right, I just do theory
I just do theory.
Why is it I can just do theory?
I aced math classes in school.
One-Ten is my favorite rule.
Intractability’s really cool.
I’ve been unplugging while you were debugging.
Your Windows crashed, your hard disk’s whirring,
But my platforms all are Turing.
Not a lot of exceptions get thrown
Approximating Diophantines with twelve unknowns.
I’m the department’s main instructor.
When they need a course taught, who do they ask?
I’m always up to the task.
It beats sitting on my ass.
I’m trying to cold-start my social network
Saying “Busy Beaver” with a smirk.
In blogs and galleries I do lurk.
Understand, yo? I’m searching for that Big O.
My grandest conceit is that my brain is PSPACE-complete.
My calculus is lambda and my math is discrete.
The only problem that ever made me halt
Was whether Samson or Delilah won by default.
My core hypotheses are unfounded.
All my measures are resource-bounded.
They see me struggling with BASIC.
They feel sorry because I just do theory.
Yes, it’s true, I just do theory.
Yes, it’s true, I just do theory.
All because I just do theory.
BQP, I just do theory.
I wanna code with the hackers
But oh well, they can tell I just do theory.
I just do theory.
I just do theory.
Yes, I just do theory.
QED, I just do theory.
Fabulous!!
ReplyDeleteOn my Mac/Firefox, the Weird Al page got confused and played "I'll Sue Ya!". So here's a direct YouTube "White & Nerdy" link. It has some visual references to the original "Riding Dirty" video.
This is pretty well polished, and I especially like the lines with "unnatural" thru "Karp-Lipton advice", "LaTeX...checkable", "on RA, while I'm teaching", "platforms...unknowns", and the way resource-bounded measure got worked in.
There's an information theory song at the end of this article. Will that do?
ReplyDeleteCorrection: The information theory song was on page 12.
ReplyDeleteSomeone old (like me) should remind everybody of the marvelous version of Billy Joel's "For the longest time" that Richard Beigel (or his students) designed a few years back.
ReplyDeleteRecollecting from memory,
"If you prove P is NP tonight / there will still be papers left to write / I have a witness / checking for completeness / forever following the longest path /uh-uh-uh / find the longest path"
(and it went on... there was a great "women too" in the chorus somewhere, don't miss it)
JLBalcazar