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.

  • 2
    $\begingroup$ Have you tried just asking Professor Pippenger? $\endgroup$
    – Joe
    Feb 18 '12 at 20:38
  • $\begingroup$ @Joe: I don't know him :) $\endgroup$ Feb 18 '12 at 21:41
  • $\begingroup$ 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. $\endgroup$
    – Kaveh
    Feb 18 '12 at 23:28
  • $\begingroup$ No it's not an example. I was formulating a law of reciprocity :) $\endgroup$ Feb 20 '12 at 6:59
  • 6
    $\begingroup$ @SureshVenkat I asked him for you, and posted his response in my answer below. $\endgroup$
    – Joe
    Feb 20 '12 at 17:57

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,



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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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