<p>In the paper "On Uniform Circuit Complexity" by Ruzzo, footnote 1 says</p>

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

<p>And [5] is the DCFL paper by Cook.</p>

CC BY-SA 3.0
2012-02-20T13:03:46.163Z
2012-02-20T13:03:46.163Z
Kristoffer Arnsfelt Hansen
<p>The following is according to Nick Pippenger:</p>
<blockquote>
<p>The relevant references are as follows.  Steve described NC as Nick's Class in his paper &quot;Deterministic CFL's Are Accepted Simultaneously in Polynomial Time and Log Squared Space&quot; (ACM STOC, 11 (1979) 338-345)  on SC, and I described SC as Steve's Class in my paper &quot;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.</p>
<p>Best wishes,</p>
<p>Nick</p>
</blockquote>

CC BY-SA 3.0
2012-02-20T17:55:10.850Z
2012-02-20T17:55:10.850Z
2020-06-17T09:38:08.363Z
Joe
<p>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}$.</p>

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

<p>p.s I'm asking because I was browsing <a href="http://en.wikipedia.org/wiki/List_of_examples_of_Stigler%27s_law">examples of Stigler's Law of Eponymy</a>, 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. </p>

CC BY-SA 3.0
2012-02-18T20:38:54.643Z
Have you tried just asking [Professor Pippenger](http://www.math.hmc.edu/~njp/)?
Joe
CC BY-SA 3.0
2012-02-18T21:41:23.737Z
@Joe: I don't know him :)
Suresh Venkat
CC BY-SA 3.0
2012-02-18T23:28:31.007Z
IIRC, I have heard the same story from others who were here ([UofT/DCS/theory](http://www.cs.toronto.edu/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
CC BY-SA 3.0
2012-02-20T06:59:22.633Z
No it's not an example. I was formulating a law of reciprocity :)
Suresh Venkat
CC BY-SA 3.0
2012-02-20T17:57:54.630Z
@SureshVenkat I asked him for you, and posted his response in my answer below.
Joe
<cc.complexity-theory><ho.history-overview>
"Steve's class": origin of SC
Suresh Venkat
# "Steve's class": origin of SC

(Asked by: username_0 on 2011-12-05)

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](http://en.wikipedia.org/wiki/List_of_examples_of_Stigler%27s_law), 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.

**Tags:** cc.complexity-theory, ho.history-overview
> **Comments:**
> **username_1**: Have you tried just asking [Professor Pippenger](http://www.math.hmc.edu/~njp/)?  
> **username_0**: @Joe: I don't know him :)  
> **username_2**: IIRC, I have heard the same story from others who were here ([UofT/DCS/theory](http://www.cs.toronto.edu/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.  
> **username_0**: No it's not an example. I was formulating a law of reciprocity :)  
> **username_1**: @SureshVenkat I asked him for you, and posted his response in my answer below.  

---

## 2 answers

### Answer by username_1 on 2012-02-20. Score: 29 | Accepted answer

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


---

### Answer by username_3 on 2012-02-20. Score: 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.


---

