"Kelas Steve": asal-usul SC

Kita "tahu" bahwa dinamai Steve Cook dan dinamai untuk Nick Pippenger. Jika saya tidak salah, Steve Cook memberi nama NC untuk menghormati Nick Pippenger, dan saya diberitahu bahwa kebalikannya juga benar. Namun, saya tidak dapat menemukan bukti dari fakta terakhir ini baik di makalah Steve Cook di DCFLs atau bukti Nisan bahwa . $\mathsf{SC}$ $\mathsf{NC}$ $\mathsf{RL} \subseteq \mathsf{SC}$

Apakah ada bukti terdokumentasi dari klaim yang terakhir, atau ini hanya "di udara"?

ps Saya bertanya karena saya melihat-lihat contoh Hukum Epigami Stigler , dan bertanya-tanya tentang apa yang saya sebut "Stigler Reciprocity": di mana sesuatu yang ditemukan oleh A dinamai dengan B dan sebaliknya. Contohnya adalah Matriks Cartan dan formulir Pembunuhan.

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

Sudahkah Anda mencoba bertanya pada Profesor Pippenger ?

Joe

@ Jo: Aku tidak kenal dia :)

Suresh Venkat

IIRC, saya telah mendengar cerita yang sama dari orang lain yang ada di sini ( UofT / DCS / teori ) pada saat Nick ada di sini jadi saya pikir itu benar (tapi saya belum bertanya kepada Steve). Saya tidak berpikir itu adalah contoh Hukum Epigami Stigler karena penamaannya disengaja dan tidak ada yang menghubungkan penemuan mereka dengan orang lain.

Kaveh

Tidak, itu bukan contoh. Saya sedang merumuskan hukum timbal balik :)

Suresh Venkat

@ SureshVenkat saya memintanya untuk Anda, dan memposting tanggapannya dalam jawaban saya di bawah ini.

Joe

Jawaban:

Berikut ini menurut Nick Pippenger:

Referensi yang relevan adalah sebagai berikut. Steve menggambarkan NC sebagai Kelas Nick dalam makalahnya "Deterministik CFL Diterima Secara bersamaan dalam Waktu Polinomial dan Log Squared Space" (ACM STOC, 11 (1979) 338-345) di SC, dan saya menggambarkan SC sebagai Steve's Class dalam makalah saya "Simultan Resource Bounds '' (IEEE FOCS, 20 (1979) 307-311) di NC. Tetapi nama-nama tersebut berasal sekitar satu setengah tahun sebelumnya, ketika saya mengunjungi Departemen CS Universitas Toronto (Januari hingga Juni 1978) Saat itulah studi dua kelas dimulai, dengan Steve mendefinisikan SC dan saya mendefinisikan NC, dan berbagai orang di departemen (saya pikir Allan Borodin adalah yang pertama) menggunakan dua nama. Musim gugur berikutnya, Steve menyerahkan kertas yang dikutip di atas Saya berada di komite program untuk STOC itu, dan tidak diizinkan untuk menyerahkan kertas ke sana,

Semoga sukses,

Nick

Joe
sumber

Dalam makalah "On Uniform Circuit Complexity" oleh Ruzzo, catatan kaki 1 mengatakan

Istilah Cook adalah PLOPS; SC adalah mnemonic Pippenger untuk "Steve's Class," sebagai pengakuan atas kontribusi [5]

Dan [5] adalah kertas DCFL karya Cook.

Kristoffer Arnsfelt Hansen
sumber