"Clase de Steve": origen de SC

"Sabemos" que lleva el nombre de Steve Cook y lleva el nombre de Nick Pippenger. Si no me equivoco, Steve Cook nombró a NC en honor a Nick Pippenger, y me dijeron que lo contrario también es cierto. Sin embargo, no he podido encontrar ninguna evidencia de este último hecho en el documento de Steve Cook, ya sea en DCFLs o de Nisan prueba de que . $\mathsf{SC}$ $\mathsf{NC}$ $\mathsf{RL} \subseteq \mathsf{SC}$

¿Existe alguna evidencia documentada del último reclamo, o es simplemente "en el aire"?

PD: pregunto porque estaba buscando ejemplos de la Ley de Eponimia de Stigler , y me preguntaba acerca de lo que llamaré "Reciprocidad de Stigler": donde algo inventado por A lleva el nombre de B y viceversa. Un ejemplo de esto son las matrices de Cartan y los formularios de asesinato.

cc.complexity-theory ho.history-overview Suresh Venkat
fuente

¿Has intentado preguntarle al profesor Pippenger ?

Joe

@ Joe: No lo conozco :)

Suresh Venkat

IIRC, he escuchado la misma historia de otros que estaban aquí ( UofT / DCS / teoría ) en el momento en que Nick estuvo aquí, así que creo que es verdad (pero no le he preguntado a Steve). No creo que sea un ejemplo de la Ley de Eponimia de Stigler porque el nombramiento fue intencional y nadie atribuye su descubrimiento a otra persona.

Kaveh

No, no es un ejemplo. Estaba formulando una ley de reciprocidad :)

Suresh Venkat

@SureshVenkat Le pregunté por usted y publiqué su respuesta en mi respuesta a continuación.

Joe

Respuestas:

Lo siguiente es según Nick Pippenger:

Las referencias relevantes son las siguientes. Steve describió a NC como la clase de Nick en su artículo "Las CFL deterministas se aceptan simultáneamente en el tiempo polinómico y el espacio de registro cuadrado" (ACM STOC, 11 (1979) 338-345) en SC, y describí a SC como la clase de Steve en mi artículo "Simultáneo Resource Bounds '' (IEEE FOCS, 20 (1979) 307-311) en Carolina del Norte. Pero los nombres se originaron aproximadamente un año y medio antes, cuando visité el Departamento de CS de la Universidad de Toronto (enero a junio de 1978) Fue entonces cuando comenzó el estudio de las dos clases, con Steve definiendo SC y yo definiendo NC, y varias personas en el departamento (creo que Allan Borodin fue el primero) usando los dos nombres. El otoño siguiente, Steve presentó el documento citado anteriormente Estuve en el comité del programa para ese STOC, y no me permitieron enviarle documentos,

Los mejores deseos,

Mella

Joe
fuente

En el documento "Sobre la complejidad del circuito uniforme" de Ruzzo, la nota 1 dice

El término de Cook fue PLOPS; SC es la nemotecnia de Pippenger para "Steve's Class", en reconocimiento de la contribución de [5]

Y [5] es el documento DCFL de Cook.

Kristoffer Arnsfelt Hansen
fuente