I coulda been famous, I coulda been a contender.

A PDF came across our Twitter feed today (http://www.scribd.com/doc/35539144/pnp12pt - courtesy of @arnaudsj) and it reminded me of my favourite moment in undergrad. For those who think the PDF is tl;dr - I’ll summarize quickly. The researched who authored the paper believes he has found a proof to a very difficult problem in computer science for which there is a $1 million prize. For 30-40 years, the best minds in computer science and math have tried to solve this problem. Keep that in mind as I tell you my story.In my 3rd year of computer science at York University in Toronto, my algorithms professor, Eric Ruppert, was teaching us about P and NP. He then told us about the $1 million dollar prize for anyone who could either prove or disprove P == NP. He then threw this carrot out there: “And if anyone can solve it, they get an automatic A+ and get to skip the exam.” I was getting about a C+ at the time and did not look forward to the exam (with good reason, only 3 people passed it!)So I went home that night and tried to solve the problem. I don’t remember the details, but I came up with an algorithm that wasn’t polynomial in computation time and could minimize the time needed to traverse a graph (Travelling Salesman’s problem). I was so excited, I emailed my professor telling him I’ll be in his office the next day with good news.

The next day, I strode into his office, like Caesar returning from a victorious battle, expecting to accept my reward and for the crowds of computer science groupies to throw their bras at me. My professor laughed when I told him what I thought I had come up with. So he began to find a hole in my algorithm. A few minutes went by, and he still couldn’t find a hole. I saw that he began to get a little nervous. After what seemed like an hour, but was probably only 5 minutes, he finally came up with a scenario where my algorithm failed to find the correct solution and my dreams were dashed. No A+, no automatic deferral of the final exam, and no $1 million prize. But I almost reached the summit of algorithm proficiency. Alas, like George Costanza, I flew too close to the sun on wings of pastrami.