P-time in a Bottle

Words: Bridget Spitznagel

Music: Time in a Bottle, Jim Croce

If I could prove P equals NP,
The first thing that I'd like to do
Is to go on a crawl,
Hit each pub and all, and then,
Return to C M U.

If I went through the IC forever
The scavenger hunt's what I'd do
I'd take the least time
You could measure and then, again,
Return to C M U.

  But there never seems to be a P-time
  Solution to the trav'ling sales-
  Man problem.
  I've looked around enough to see
  My favorite problems are NP,
  Can't solve them.  [At least not in polynomial time.]

I dreamed of the area parties,
the login ball and the home-brew.
I could not find one Ham-
iltonian circuit, and now
I can't reach C M U.

  There never seems to be a P-time
  Solution to the trav'ling sales-
  Man problem.
  I've looked around enough to see
  My favorite problems are NP,
  Can't solve them.  [At least not in polynomial time.]

Background: This is another algorhythmic one, inspired by a friend's fondness of the Travelling Salesman Problem and the words "in a bottle".

The IC, or immigration course, is a two-week introduction to the department for new graduate students: an opportunity to learn what all the potential advisors are up to, and a time of numerous social activities:

• One traditional activity is the scavenger hunt (teams of students visit interesting local places and photograph themselves there.)
• The "login ball" is a party for everyone at the start of the IC.
• Each area (e.g. Theory) holds an "area party", on different evenings, so that new students can talk to people in that area. After the IC, the new students must choose their advisor and area of interest, so the motive is more than partying for its own sake.
• There are varying other social/introductory events organized by students: a "living green in Pittsburgh" tour, a home-brewing event, a pub crawl..

Legal frufru: Lyrics © 1996, Bridget Spitznagel. Permission granted for private noncommercial use and reproduction of these lyrics, provided that this copyright notice remains intact. Other uses are negotiable.