„Klasa Steve'a”: pochodzenie SC

„Wiemy”, że nazwano na cześć Steve'a Cooka, a nazywa się Nick Pippenger. Jeśli się nie mylę, Steve Cook nazwał NC na cześć Nicka Pippengera i powiedziano mi, że jest też odwrotnie. Nie znalazłem jednak żadnego dowodu na ten ostatni fakt ani w pracy Steve'a Cooka na temat DCFL, ani w dowodzie Nisana, że .$\mathsf{SC}$$\mathsf{NC}$$\mathsf{RL} \subseteq \mathsf{SC}$

Czy istnieją udokumentowane dowody na to ostatnie twierdzenie, czy jest to po prostu „w powietrzu”?

ps Pytam, ponieważ przeglądałem przykłady prawa eponimii Stiglera i zastanawiałem się nad tym, co nazywam „wzajemnością Stiglera”: gdzie coś wymyślonego przez A nosi nazwę B i odwrotnie. Przykładem tego są Matryce Cartana i formularze zabijania.

Poniższe jest według Nicka Pippengera:

Odpowiednie odniesienia są następujące. Steve opisał NC jako klasę Nicka w swoim artykule „Deterministyczne CFL są akceptowane jednocześnie w czasie wielomianowym i logarytmicznej kwadratowej przestrzeni” (ACM STOC, 11 (1979) 338-345) na SC, a SC opisałem jako klasę Steve'a w moim artykule „Jednoczesne Resource Bounds '' (IEEE FOCS, 20 (1979) 307-311) o NC. Ale nazwy powstały około półtora roku wcześniej, kiedy odwiedziłem Wydział CS Uniwersytetu University of Toronto (od stycznia do czerwca 1978 r.) Właśnie wtedy rozpoczęły się badania dwóch klas, w których Steve zdefiniował SC, a ja NC, a różne osoby w dziale (myślę, że Allan Borodin był pierwszy) posługiwały się tymi dwoma nazwami. Następnej jesieni Steve przedstawił artykuł cytowany powyżej Byłem w komitecie programowym dla tego STOC i nie pozwoliłem mu przesyłać dokumentów,

Wszystkiego najlepszego,

Nacięcie

W artykule „On Uniform Circuit Complexity” Ruzzo napisano w przypisie 1

Cookem był PLOPS; SC jest mnemonikiem Pippengera dla „klasy Steve'a” w uznaniu wkładu [5]

A [5] to papier DCFL autorstwa Cooka.