As a grad student in the late 80's I had the opportunity to witness many great and often surprising theorems in computational complexity. Let me tell you about one of them, the Immerman-Szelepcsényi result that nondeterministic space is closed under complement. I wish I had the original emails for this story but instead I'm working from memory and apologies if I get some of the details wrong. I'm expanding from a short version from the early days of this blog.
I started my graduate work at UC Berkeley in 1985 and then moved to MIT in the summer of '86, following my advisor Michael Sipser. In the summer of 1987, Neil Immerman, then at Yale, proved his famous result building on his work in descriptive complexity In those days you didn't email papers, he made copies and sent them by US postal mail to several major researchers in complexity including Sipser. But Sipser was away for the summer, I believe in Russia, and the paper sat in his office.
Immerman also sent the paper to a Berkeley professor, probably Manuel Blum, who gave it to one of his students who decided to speak about the result in a student-led seminar. I forgot who was the student, maybe Moni Naor. I was still on the Berkeley email list so I got the talk announcement and went into complexity ecstasy over the news. I asked Moni (or whomever was giving the talk) if he could tell me details and he sent me a nice write-up of the proof. Given the importance of the result, I sent the proof write-up out to the MIT theory email list.
Guess who was on the MIT theory list? Neil Immerman. Neil wrote back with his own explanation of the proof. Neil explained how it came out of descriptive complexity but as a pure write-up of a proof of the theorem, Moni did an excellent job.
We found out about Robert Szelepcsényi when his paper showed up a few months later in the Bulletin of the European Association for Theoretical Computer Science. Szelepcsényi came to the problem from formal languages, whether context-sensitive languages (nondeterministic linear space) was closed under complement. Szelepcsényi, an undergrad in Slovakia at the time, heard about the problem in a class he took. Szelepcsényi's proof was very similar to Immerman. Szelepcsényi's paper took longer to get to US researchers but likely was proven and written about the same time as Immerman.
Even though both papers were published separately we refer to the result as Immerman-Szelepcsényi and is now just some old important theorem you see in introductory theory classes.
I am sure that Immerman and Sz... worked independly and kudos to both of them!
ReplyDeleteIf this happened now it would be much harder to prove ind. since the paper would be on arXiv available for all!
Another interesting bit of context was a precursor paper by Jenner, Kirsig, and Lange published at ICALP 1987 which showed the weaker but surprising and suggestive result that the alternating logspace hierarchy collapses at the 2nd level. At its heart it did use counting, which is also used in Immerman's and Szelepcsenyi's much stronger arguments, though its use is much less transparent than in either later paper. Immerman clearly was inspired by that paper; Szelepcsenyi clearly had no idea about it and does not cite it.
ReplyDeleteShortly before I&S Schoening and Wagner collapsed the logarithmic oracle hierarchy, which implied the collapse
Deleteof the alternation hierarchy.- It is relatively unknown that already in December 86 Toda had a JCSS-paper collapsing some linear space hierachy to its second level. k-jl
Thanks all for sharing these interesting bits of history, and thanks for mentioning Toda's paper. It's very interesting. Maybe it is considered a folklore result now but I did not know about the collapse of the alternating space hierarchy. The wikipedia page on Alternating Turing Machines does not mention the result either.
ReplyDeleteI learned complexity theory under Immerman a couple years ago. Although he did not mention this part of the story, he did mention that he discovered the result while walking his dog.
ReplyDelete