"Steve's class": Herkunft von SC

Wir "wissen", dass nach Steve Cook und nach Nick Pippenger benannt ist. Wenn ich mich nicht irre, hat Steve Cook NC zu Ehren von Nick Pippenger genannt, und mir wurde gesagt, dass auch das Gegenteil der Fall ist. Allerdings konnte ich weder in Steve Cooks Aufsatz über DCFLs noch in Nisans Beweis, dass Beweise für diese letztere Tatsache finden . $\mathsf{SC}$ $\mathsf{NC}$ $\mathsf{RL} \subseteq \mathsf{SC}$

Gibt es irgendwelche dokumentierten Beweise für die letztgenannte Behauptung oder liegt dies nur "in der Luft"?

ps Ich frage , weil ich Beispiele von Stiglers Eponymie-Gesetz durchgesehen und mich gefragt habe, was ich "Stigler-Reziprozität" nennen werde: Wo etwas, das von A erfunden wurde, nach B benannt ist und umgekehrt. Ein Beispiel hierfür sind Cartan-Matrizen und Tötungsformen.

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

Haben Sie versucht, nur Professor Pippenger zu fragen ?

Joe

@ Joe: Ich kenne ihn nicht :)

Suresh Venkat

IIRC, ich habe die gleiche Geschichte von anderen gehört, die zu der Zeit hier waren ( UofT / DCS / Theorie ), als Nick hier war, also denke ich, dass es wahr ist (aber ich habe Steve nicht gefragt). Ich glaube nicht, dass es ein Beispiel für Stiglers Eponymiegesetz ist, weil die Benennung absichtlich war und niemand ihre Entdeckung jemand anderem zuschreibt.

Kaveh,

Nein, es ist kein Beispiel. Ich formulierte ein Gesetz der Gegenseitigkeit :)

Suresh Venkat

@ SureshVenkat Ich habe ihn nach dir gefragt und seine Antwort in meiner Antwort unten gepostet.

Joe

Antworten:

Das Folgende ist laut Nick Pippenger:

Die relevanten Referenzen lauten wie folgt. Steve beschrieb NC in seiner Arbeit "Deterministische CFLs werden gleichzeitig in Polynomial Time und Log Squared Space akzeptiert" (ACM STOC, 11 (1979) 338-345) als Nicks Klasse und ich beschrieb SC in meiner Arbeit "Simultaneous" als Steves Klasse Resource Bounds '' (IEEE FOCS, 20 (1979) 307-311) auf NC. Aber die Namen entstanden ungefähr eineinhalb Jahre zuvor, als ich die CS-Abteilung der Universität von Toronto besuchte (Januar bis Juni 1978). Englisch: emagazine.credit-suisse.com/app/art ... = 157 & lang = en Zu diesem Zeitpunkt begann das Studium der beiden Klassen, in dem Steve SC und ich NC definierten und verschiedene Mitarbeiter der Abteilung (ich glaube, Allan Borodin war der erste) die beiden Namen verwendeten Ich war im Programmkomitee für dieses STOC und durfte keine Papiere einreichen,

Die besten Wünsche,

Nick

Joe
quelle

In der Arbeit "On Uniform Circuit Complexity" von Ruzzo heißt es in Fußnote 1

Cooks Amtszeit war PLOPS; SC ist Pippengers Mnemon für "Steve's Class" in Anerkennung des Beitrags von [5]

Und [5] ist das DCFL-Papier von Cook.

Kristoffer Arnsfelt Hansen
quelle