Saya punya dua pertanyaan historis:
Siapa yang pertama kali menggambarkan perhitungan nondeterministik?
Saya tahu bahwa Cook menjelaskan masalah NP-complete, dan bahwa Edmonds mengusulkan bahwa algoritma P adalah "efisien" atau "baik" algoritma.
Aku mencari ini artikel Wikipedia dan skim "Di Komputasi Kompleksitas Algoritma," tapi tidak bisa menemukan referensi untuk saat perhitungan nondeterministic pertama kali dibahas.
Apa referensi pertama ke NP kelas? Apakah itu makalah Cook tahun 1971?
Jawaban:
Saya selalu melihat gagasan nondeterminisme dalam perhitungan yang dikaitkan dengan Michael Rabin dan Dana Scott. Mereka mendefinisikan automata terbatas nondeterministik dalam makalah terkenal mereka, Finite Automata dan Masalah Keputusan mereka , 1959. Kutipan Penghargaan Turing dari Rabin juga menunjukkan bahwa Rabin dan Scott memperkenalkan mesin nondeterministik.
sumber
Inilah yang dikatakan Odifreddi tentang masalah ini:
Perhatikan bahwa gagasan nondeterminisme dalam arti "ada + verifikasi" ada dalam teori komputabilitas jauh sebelum teori kompleksitas, misalnya bentuk normal Kleene , hierarki aritmetika . Model komputasi lain seperti sistem kanonik Post (dikenal setidaknya sejak 1943) dan tata bahasa juga tidak deterministik. Saya pikir orang bahkan dapat mendorong gagasan ke waktu kalkulus epsilon dan operator pilihan Hilbert .
Tentang NP, saya bertanya kepada Steve Cook. Nama NP untuk kelas masalah komputasi waktu polinomial nondeterministik diperkenalkan oleh Richard Karp dalam makalahnya yang terkenal tahun 1972. Masak mengacu pada kelas Tyn masalah waktu komputer mesin nondeterministic masalah dihitung dalam kertas 1971 yang terkenal yang mendefinisikan pengurangan waktu polinomial dan menunjukkan bahwa ada masalah lengkap, tetapi tanpa memberi nama kepada kelas.
Sebelum makalahnya tidak ada banyak minat dalam masalah yang dapat dihitung dalam waktu polinomial oleh mesin Turing nondeterministic, hanya setelah kertas Karp menjadi jelas bahwa begitu banyak masalah alam di NP. Setelah makalah Cook, beberapa orang tertarik, terutama dua yang sejak awal tertarik (sebelum makalah Karp keluar) adalah Michael Rabin dan Allan Borodin .
Tulisan Karp tahun 1972 mengejutkan orang-orang dengan menunjukkan betapa kelengkapan NP-nya adalah masalah alami.
sumber
Rabin dan Scott memperkenalkan automata terbatas nondeterministik dengan makalah penelitian mereka yang diterbitkan dalam jurnal IBM, April 1959. Dalam makalah mereka menyebutkan:
Seluruh kertas dapat dilihat di sini: http://www.cse.chalmers.se/~coquand/AUTOMATA/rs.pdf
sumber