„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 .
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.
cc.complexity-theory
ho.history-overview
Suresh Venkat
źródło
źródło
Odpowiedzi:
Poniższe jest według Nicka Pippengera:
źródło
W artykule „On Uniform Circuit Complexity” Ruzzo napisano w przypisie 1
A [5] to papier DCFL autorstwa Cooka.
źródło