"Steve's class": origin of SC

Question

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.

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 06:59
@SureshVenkat I asked him for you, and posted his response in my answer below. — Joe, Feb 20 '12 at 17:57

score 29 · Accepted Answer · edited Jun 17 '20 at 09:38

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

score 7 · Answer 2 · answered Feb 20 '12 at 13:03

7

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.

answered Feb 20 '12 at 13:03

Kristoffer Arnsfelt Hansen

4,159
2
26
36

"Steve's class": origin of SC

2 Answers2

Linked