Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

We "know" that $\mathsf{SC}$ is named for Steve Cook and $\mathsf{NC}$ is named for Nick Pippenger. If I'm not mistaken, Steve Cook named NC in honor of Nick Pippenger, and I was told that the reverse is true as well. However, I wasn't able to find any evidence of this latter fact in either Steve Cook's paper on DCFLs or Nisan's proof that $\mathsf{RL} \subseteq \mathsf{SC}$.

Is there any documented evidence of the latter claim, or is this merely "in the air" ?

p.s I'm asking because I was browsing examples of Stigler's Law of Eponymy, and was wondering about what I'll call "Stigler Reciprocity": where something invented by A is named after B and vice versa. An example of this is Cartan Matrices and Killing forms.

share|improve this question
2  
Have you tried just asking Professor Pippenger? –  Joe Feb 18 '12 at 20:38
    
@Joe: I don't know him :) –  Suresh Venkat Feb 18 '12 at 21:41
    
IIRC, I have heard the same story from others who were here (UofT/DCS/theory) at the time that Nick was here so I think it is true (but I haven't asked Steve). I don't think it is an example of Stigler's Law of Eponymy because the naming was intentional and no one is attributing their discovery to someone else. –  Kaveh Feb 18 '12 at 23:28
    
No it's not an example. I was formulating a law of reciprocity :) –  Suresh Venkat Feb 20 '12 at 6:59
5  
@SureshVenkat I asked him for you, and posted his response in my answer below. –  Joe Feb 20 '12 at 17:57
add comment

2 Answers

up vote 24 down vote accepted

The following is according to Nick Pippenger:

The relevant references are as follows. Steve described NC as Nick's Class in his paper "Deterministic CFL's Are Accepted Simultaneously in Polynomial Time and Log Squared Space" (ACM STOC, 11 (1979) 338-345) on SC, and I described SC as Steve's Class in my paper "Simultaneous Resource Bounds'' (IEEE FOCS, 20 (1979) 307-311) on NC. But the names originated about a year-and-a-half earlier, when I visited the University of Toronto CS Department (January through June, 1978). That's when the study of the two classes began, with Steve defining SC and me defining NC, and various people in the department (I think Allan Borodin was the first) using the two names. The following fall, Steve submitted the paper cited above. I was on the program committee for that STOC, and not allowed to submit papers to it, so my paper appeared in the following FOCS conference.

Best wishes,

Nick

share|improve this answer
add comment

In the paper "On Uniform Circuit Complexity" by Ruzzo, footnote 1 says

Cook’s term was PLOPS; SC is Pippenger’s mnemonic for “Steve’s Class,” in recognition of the contribution of [ 5 ]

And [5] is the DCFL paper by Cook.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.