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

2 Answers 2


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 and acknowledge you have read our privacy policy.

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