Wednesday, November 20, 2002

Where was Cook's Talk?

In 1971, Steve Cook gave his conference presentation that showed that SAT was NP-complete. There it did not immediately stir up much excitement but it is, in retrospect, the single most important conference talk in this history of theoretical computer science. So when and where was this talk?

Steve Cook's paper The Complexity of Theorem Proving Procedures appeared at the Third Annual ACM Symposium on Theory of Computing (STOC) that was held May 3-5, 1971 in Shaker Heights, Ohio, a suburb of Cleveland.

Funda Ergun, a professor at Case Western Reserve, just purchased a house in Shaker Heights and wondered where exactly the conference took place. We got the answer from Bill Rounds, who was one of the local organizers of that conference.

It was (at I think Stouffer's hotel) at the intersection of Warrensville Center Road and Chagrin Boulevard, in the Van Aken center district. The hotel is now gone.

Here is a Mapquest map of that location.

Someday we will organize a P versus NP workshop in that area and make a pilgrimage to this site.

No comments:

Post a Comment