Monday, September 21, 2009
So I open up the article about the P vs NP problem in the August 2009 Communications of the ACM and see the phrase, "since Steve Cook presented his seminal NP-completeness paper 'The Complexity of Theorem-Proving Procedures' in Shaker Heights, OH in early May, 1971." I knew about the paper, of course, and I might even have been able to tell you that it was published in 1971, but this is the first time I ever noticed the location of the conference. Why does that matter? Because I was about three miles away at the time (possibly closer, depending on exactly when during the conference Cook gave his talk). According to this post from a few years ago, the 1971 Symposium on Theory of Computation was held at the Stouffer's hotel at the intersection of Warrensville and Van Aken (Northfield and Chagrin come in there too -- it's a huge, nasty intersection...). I remember being driven by that hotel quite often as a child. Of course, I didn't manage to attend STOC itself; at the time, as a Kindergartner, I think it might have been over my head. As I recall, I was still spending a certain amount of time hiding in the closet of my classroom. One month later, my world was shaken by an event of much greater significance than the introduction of the concept of NP-completeness: I got chicken pox and missed the last week of school, including the celebration for all of the over-the-summer birthdays (including mine).