Mengapa waktu polinomial disebut "efisien"?

Mengapa dalam ilmu komputer setiap kompleksitas yang paling banyak jumlahnya dianggap efisien?

Untuk setiap aplikasi praktis ^(a) , algoritma dengan kompleksitas jauh lebih cepat daripada algoritma yang berjalan dalam waktu, katakanlah, n 80 , tetapi yang pertama dianggap tidak efisien sementara yang kedua efisien. Dimana logikanya ?!$n^{\log n}$$n^{80}$

^{(a) Anggaplah, misalnya, jumlah atom di alam semesta sekitar .$10^{80}$}

Perspektif lain tentang "efisiensi" adalah waktu polinomial memungkinkan kita untuk mendefinisikan gagasan "efisiensi" yang tidak bergantung pada model mesin. Secara khusus, ada varian dari tesis Gereja-Turing yang disebut "tesis Gereja-Turing efektif" yang mengatakan bahwa setiap masalah yang berjalan dalam waktu polinomial pada jenis model mesin juga akan berjalan dalam waktu polinomial pada model mesin lain yang sama kuatnya.

Ini adalah pernyataan yang lebih lemah untuk tesis CT umum, dan 'semacam' dilanggar oleh kedua algoritma acak dan algoritma kuantum, tetapi belum dilanggar dalam arti mampu memecahkan masalah NP-hard dalam waktu bersamaan dengan mengubah model mesin.

Ini pada akhirnya adalah alasan mengapa waktu polinomial adalah gagasan populer dalam theoryCS. Namun, kebanyakan orang menyadari bahwa ini tidak mencerminkan "efisiensi praktis". Untuk lebih lanjut tentang ini, posting Dick Lipton tentang ' algoritma galaksi ' adalah bacaan yang bagus.

$O(n^{80})$$O(n^{\log n})$$n > 1208925819614629174706176$

$n^{\log n}$$n^{80}$

Misalnya, sebagian besar pustaka untuk perkalian bilangan bulat, misalnya GMP akan menerapkan campuran algoritma, dan memilih algoritma inferior berdasarkan ukuran input pilih algoritma yang secara praktis unggul berdasarkan pada ukuran input, meskipun algoritma ini mungkin inferior tanpa asimptotik. Beberapa algoritma "inferior" asimptotik akan lebih cepat pada ukuran input tertentu, dan akan dipilih melalui algoritma optimal.

$O(n^{2.3737})$

Teori TL; DR memperhatikan perilaku asimptotik untuk membandingkan algoritme ketika batas ukuran input digunakan untuk jumlah besar yang sewenang-wenang.

Jawaban ini akan melihat konteks "gambaran yang lebih besar" dari pertanyaan Anda. Ilmu komputer sebenarnya adalah ilmu yang relatif muda dan agak terbuka dan belum memiliki jawaban yang bagus atau bahkan bagus untuk beberapa pertanyaan mendasar & mendasar. Pertanyaan dasar "apa yang dihitung secara efisien" adalah akurat atau kasar diformalkan dalam CS (tergantung pada pendapat) sebagai masalah P vs NP yang terkenal (atau masalah P vs Exptime yang terkait erat), dan masih terbuka setelah lebih dari empat dekade yang awalnya diperkenalkan oleh Cook / Levin ~ 1970 dan kerja keras oleh para ilmuwan komputer terhebat dunia (dan banyak ahli matematika juga tertarik pada masalah ini sebagai hal yang mendasar).

Jadi dengan kata lain, bahkan dengan definisi kasar "efisien" sebagai waktu P, dan salah satu penghargaan ilmiah bernilai tertinggi - yaitu penghargaan $ 1 juta yang melekat pada masalah selama lebih dari 10 tahun - ilmu komputer bahkan tidak dapat membuktikan bahwa beberapa masalah (dekat dengan batas ini) harus atau tidak harus memiliki algoritma (Ptime) yang efisien. Oleh karena itu definisi tepat "efisien" lebih tepat daripada waktu P tidak diperlukan atau bahkan mungkin saat ini. Jika / ketika dugaan P vs NP diselesaikan dengan satu atau lain cara, definisi yang lebih ketat dari "efisien" mungkin atau mungkin akan dimungkinkan.

Selain itu, orang mungkin merasa bahwa definisi Ptime dari "efisien" bahkan mungkin sedikit "ceroboh", dan kebanyakan ilmuwan komputer mungkin akan setuju, dan hampir semua dari mereka berpikir dugaan P vs NP adalah yang paling penting untuk diselesaikan, untuk titik bahwa mereka bahkan mungkin menganggap pernyataan atau pengamatan ini sebagai sepele .... dengan kata lain, bisa dikatakan, ini adalah pekerjaan yang sedang berjalan / kami sedang mengusahakannya . (bahkan para ilmuwan komputer arus utama bahkan melangkah sejauh ini, hanya setengah bercanda, untuk secara rutin menyebut kesenjangan & kurangnya kemajuan / pemisahan yang pasti sebagai hal yang memalukan .)

Bahkan ada dugaan yang berhubungan erat / secara signifikan lebih kuat dari P vs NP, yaitu NP vs P / poly, yang juga tidak dapat diselesaikan oleh ilmu komputer saat ini. itu dugaan bahwa masalah NP-kali tidak dapat diselesaikan dengan setiap sirkuit "P berukuran", yaitu bahkan tidak terbatas pada mereka sirkuit yang bisa diciptakan oleh algoritma / mesin Turing.

Adapun seberapa keras P vs NP mungkin - ada beberapa alasan kuat untuk berpikir itu mungkin setidaknya sekeras dugaan Riemann yang sangat tua dalam matematika (sekarang 1,5 abad ), karena keduanya telah memiliki penghargaan $ 1 juta yang sama untuk lebih dari satu dekade, dan belum ada yang diselesaikan / pertama.

Jadi dengan kata lain, untuk mendefinisikan secara tepat algoritma apa yang benar-benar "efisien" sebenarnya adalah salah satu masalah terbuka yang paling penting & paling sulit yang ada dalam sains dan matematika teoretis .

Sebenarnya pertanyaan tentang "apa yang dihitung secara efisien" sebenarnya bahkan lebih halus, karena ada varian tesis Church-Turing yang disebut tesis CT P-time, dan tidak diketahui apakah komputasi kuantum benar-benar melanggarnya . Dengan hasil terobosan Shor dari P-time QM, anjak dianggap twist dramatis dalam penelitian ini. Dengan kata lain, masalah apa yang dihitung secara efisien sebenarnya masuk akal turun ke jalan ke prinsip-prinsip fisika yang mendalam, dan berkaitan dengan apakah komputasi kuantum dapat menghitung lebih efisien daripada perhitungan klasik, yang juga merupakan masalah yang umumnya terbuka dalam CS teoritis dan fisika maju.

Jadi orang bahkan dapat menambahkan bahwa P vs NP & pertanyaan tentang komputasi yang efisien mungkin sangat penting atau mendasar untuk di-tambah dengan CS dan matematika- fisika .

[1] Masalah P vs NP, wikipedia

[2] Masalah hadiah milenium

[3] Kelas P / Poli, wikipedia

[4] Algoritma Shor

Algoritma waktu polinomial dianggap efisien hanya jika dibandingkan dengan waktu non-polinomial yang paling sulit, terutama yang disebut NP-Lengkap. Lihat gambar: Diagram Euler untuk set masalah P, NP, NP-complete, dan NP-hard .