„Klasa Steve'a”: pochodzenie SC

33

„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 .SCNCRLSC

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.

Suresh Venkat
źródło
2
Próbowałeś właśnie zapytać profesora Pippengera ?
Joe
@Joe: Nie znam go :)
Suresh Venkat
IIRC, słyszałem tę samą historię od innych, którzy byli tutaj ( UofT / DCS / teoria ) w czasie, gdy Nick był tutaj, więc myślę, że to prawda (ale nie zapytałem Steve'a). Nie sądzę, że jest to przykład prawa eponimii Stiglera, ponieważ nazewnictwo było celowe i nikt nie przypisuje swojego odkrycia komuś innemu.
Kaveh
Nie, to nie jest przykład. Sformułowałem prawo wzajemności :)
Suresh Venkat
6
@SureshVenkat Poprosiłem go o ciebie i zamieściłem jego odpowiedź w mojej odpowiedzi poniżej.
Joe

Odpowiedzi:

28

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

Joe
źródło
7

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.

Kristoffer Arnsfelt Hansen
źródło