In the afternoon of May 4, 1971, in the Stouffer's Somerset Inn in Shaker Heights, Ohio, Steve Cook presented his STOC paper proving that Satisfiability is NP-complete and Tautology is NP-hard.
The theorems suggest that Tautology is a good candidate for an interesting set not in [P] and I feel it is worth spending considerable effort trying to prove this conjecture. Such a proof would be a major breakthrough in complexity theory.And thus Cook formulated what was soon to be called the P versus NP problem. The rest is history.
Here's the 1971 STOC Program (there were 143 attendees) and what that sacred ground looks like today.
I like the poem at the bottom of page 3! ;-)
ReplyDeleteThe present topic on Dick Lipton and Ken Regan's Gödel's Lost Letter weblog is the role of guessing in defining (and separating) the complexity classes P and NP. This was a natural venue to ask for a short and (hopefully) nontechnical exposition of the role in complexity theory of Jules Hartmanis' "mystery languages" and the PTIME Turing machines that recognize them.
ReplyDeleteIf any readers of Computational Complexity care to attempt a response, their exposition would find at least one attentive reader ... after 40 years, there sure are a lot of mysteries ... particularly for us non-experts.
Anon1: what poem are you talking about?
ReplyDeleteI guess it has been a while ... it's now "Shaker Gardens Nursing and Rehabilitation Center"
ReplyDeleteWere there no best paper awards back then? (Even if they were I am not sure Cook's paper would've generated enough excitement, not before Karp's, but I am curious.)
ReplyDeleteAnon 2: The poem is
ReplyDeleteA finite automaton knows
That counting takes fingers and toes,
But, footless and handless,
It tries, never endless,
To follow five l's with five O's.
It would be great if Bill (or someone else) can conduct another opinion poll on P vs NP.
ReplyDeleteThe previous poll was done almost 10 years ago and it will be interesting to see how people's opinions changed since then.
Best student paper awards (FOCS only) started with the Machtey Award in 1981. STOC did not have a comparable one until the Daniel W. Lewin best student paper award was started in 2002 after the MIT student and Akamai co-founder who died in one of the planes that hit the World Trade Center on 9/11.
ReplyDeleteBest paper awards at FOCS/STOC did not exist until 2002 FOCS. The PC may choose up to 3 papers but may also decline to give any best paper award.