Apa makalah ilmu komputer pertama yang menggunakan kompleksitas waktu asimptotik?

Kapan O besar digunakan pertama kali dalam ilmu komputer dan kapan itu menjadi standar? Halaman Wikipedia tentang ini mengutip Knuth, Big Omicron dan Big Omega Dan Big Theta , SIGACT April-Juni 1976, tetapi awal tulisan itu berbunyi

Sebagian besar dari kita telah terbiasa dengan gagasan menggunakan notasi untuk berdiri untuk setiap fungsi yang besarnya dibatasi oleh waktu konstan f ( n ) , untuk semua besar n .$O(f(n))$$f(n)$$n$

Kutipan ini menunjukkan bahwa ide dan notasi sudah umum digunakan.

Halaman Wikipedia juga mengutip makalah matematika dari akhir 1800-an dan awal 1900-an, tetapi itu tidak cukup menjawab pertanyaan. Secara khusus, saya pernah mendengar para peneliti yang ada saat itu (di tahun 60-an dan 70-an, bukan di akhir 1800-an) mengatakan bahwa ketika analisis asimptotik pertama kali digunakan, beberapa orang mundur, mengatakan bahwa waktu jam dinding adalah metrik yang lebih baik. Namun, tidak seorang pun yang saya ajak bicara dapat mengutip makalah spesifik yang mendapat pushback seperti ini dan saya ingin menemukan bukti yang dapat mengkonfirmasi atau menyangkal cerita-cerita ini.

dengan pertanyaan sejarah biasanya ada nuansa halus dan tidak mudah untuk menentukan makalah tertentu yang memperkenalkan konsep tertentu karena cenderung tersebar di banyak kontributor dan kadang-kadang ditemukan kembali secara independen ketika referensi awal yang tidak jelas tidak perlu disebarluaskan (ide-ide mendasar seperti itu) . tetapi pada dasarnya sejarah berjalan seperti ini: Notasi Landau adalah formalisme matematika lama (1894 / Bachman) [1] yang diimpor ke CS sebagai "konsep kunci" sekitar awal 1970-an. pada pertengahan 1970-an ini agak diterima seperti dalam referensi Knuth Anda dan Knuth sendiri terlibat dalam menyebarkan konsep ini.

Menariknya impornya ke CS mungkin terkait erat dengan perbedaan P vs NP vs Exptime yang ditemukan pada awal 1970-an yang sangat berpengaruh / digembar-gemborkan di lapangan. Cobham / Edmonds yang mulai mendefinisikan kelas P pada awal 1970-an. [3] ada bukti awal tentang Exptime dan Expspace oleh Stockmeyer / Meyer. [2] teorema Cook-Levin [4] (1971) menunjukkan relevansi inti dari waktu P vs NP, segera didukung oleh Karp [5] (1972).

seorang ahli matematika awal yang bekerja dalam teori bilangan tetapi juga di tepi ilmu komputer adalah Pocklington. seperti pada [3] itu menunjukkan:

Namun, HC Pocklington, dalam makalah 1910, [11] [12] menganalisis dua algoritma untuk memecahkan kongruensi kuadratik, dan mengamati bahwa seseorang membutuhkan waktu "sebanding dengan kekuatan logaritma modulus" dan membandingkannya dengan yang membutuhkan waktu. proporsional "dengan modulus itu sendiri atau akar kuadratnya", sehingga secara eksplisit menggambar perbedaan antara algoritma yang berjalan dalam waktu polinomial versus yang tidak.

pelopor awal lain dalam menganalisis kompleksitas algoritma berbasis mesin untuk teori bilangan, yaitu anjak piutang, adalah Derrick Lehmer, profesor matematika di University of California, Berkeley, dan membangun / menganalisis "algoritma" anjak piutang (implementasi berbasis saringan) pada awal 1920-an dan mungkin saja dia menggambarkan sesuatu seperti kompleksitas komputasi dan anjak secara informal. [6]

namun kasus lain adalah "hilang" 1956 surat oleh Godel untuk von Neumann berbicara tentang pengukuran kompleksitas langkah f (n) dari mesin untuk menemukan bukti ukuran n . [7]

[1] Sejarah notasi O besar / wikipedia

[2] Masalah kata membutuhkan waktu eksponensial. / Stockmeyer, Meyer (1973)

[3] P sejarah kelas waktu / wikipedia

[4] teorema Cook-Levin / wikipedia

[5] Karps 21 NP menyelesaikan masalah / wikipedia

[6] Mesin factoring Lehmer / ayakan / wikipedia

[7] Godels kehilangan surat / RJLipton