Koleksi

P vs NP, NP-Complete, dan Algoritma untuk Segala-galanya

P vs NP, NP-Complete, dan Algoritma untuk Segala-galanya

Ini adalah artikel keenam dalam siri tujuh bahagian mengenai Algoritma dan Pengiraan, yang meneroka bagaimana kita menggunakan nombor binari mudah untuk menggerakkan dunia kita. Artikel pertama, Bagaimana Algoritma Menjalankan Dunia yang Kita Lalui, boleh didapati di sini.

Ketika kita duduk untuk mencuba dan menyelesaikan masalah, sangat sedikit dari kita yang berusaha untuk mengetahui jenis masalah yang sedang kita cuba selesaikan. Dalam hampir setiap kes, jawapan untuk soalan itu adalah latihan yang menarik dan bahkan dapat membantu anda menyelesaikan masalah dalam beberapa kes, tetapi tidak banyak lagi. Tetapi situasinya sangat berbeza dengan masalah seperti Traveling Salesman Problem, sebab itulah ia menjadi subjek kajian dan penyelidikan oleh saintis komputer dan ahli matematik. Ia mempunyai semuanya ada kaitan dengan pengelasannya sebagai masalah.

Mengelaskan Masalah: P Vs NP

Masalah yang kita ketahui algoritma yang cekap yang mampu menghasilkan penyelesaian dalam masa polinomial dikelaskan sebagai Masalah PP bermaksud masa polinomial, dalam contoh ini. Ini jelas merupakan sekumpulan masalah pertama yang dapat kami klasifikasikan: dari semua masalah ini di luar sana, sekurang-kurangnya kami berjaya menyelesaikannya di sini. Perkara seperti menyusun senarai, menyeimbangkan pokok, menyulitkan data adalah semua masalah yang mempunyai algoritma yang cekap dan termasuk dalam subset P.

Kemudian, kami menemui subset masalah lain yang P itu sendiri adalah sebahagian daripada, Masalah NP. The NP bermaksud masa polinomial yang tidak menentu, tetapi untuk tujuan kami, anda tidak perlu terlalu banyak mengetahui maksudnya kecuali bahagian sains sains era Turing yang mendasari yang menyokong setiap komputer moden. Apa yang anda perlu tahu ialah Masalah NP tidak mempunyai algoritma yang diketahui yang dapat menghasilkan hasil dalam masa polinomial.

Walau bagaimanapun, jika anda diberi penyelesaian untuk Masalah NP, mengesahkan bahawa betul adalah mudah dan boleh dilakukan di masa polinomial atau kurang. Kami menggunakan fakta ini setiap kali kami membuka kunci iPhone atau menghantar mesej melalui WhatsApp. Ternyata, Masalah NP sangat sesuai untuk penyulitan; hanya ada satu cara untuk menyelesaikan masalah yang membuka kunci penyulitan dengan cepat, anda perlu mempunyai jawapan terlebih dahulu.

BERKAITAN: 7 ALGORITMA PENTING YANG MENJALANKAN DUNIA

Secara semula jadi, kami suka penyulitan, dan kami gembira kerana ia selamat buat masa ini, tetapi terdapat banyak masalah di NP bahawa kita benar-benar memerlukan algoritma yang cekap. Walaupun terdapat usaha terbaik dari beberapa orang yang sangat pintar, namun, hanya ada sedikit kemajuan dalam menyelesaikan semua kecuali sangat sedikit Masalah NP yang kita tahu. Ini telah menghasilkan salah satu masalah matematik dan komputasi yang tidak dapat diselesaikan selama 50 tahun yang lalu: P vs NP, juga dipanggil P = NP.

Apa yang diminta oleh persamaan ini boleh diberikan Masalah NP diselesaikan dalam masa polinomial, sehingga menjadikannya Masalah NP sungguh Masalah P yang hanya perlu diselesaikan dengan betul, atau ada Masalah NP yang tidak dapat dijumpai penyelesaian dalam masa polinomial dan dengan demikian tetap tidak dapat diselesaikan secara praktikal tidak kira algoritma apa yang kita kembangkan?

Apabila melihat dua masalah ini, P vs NP, tujuannya adalah untuk membuktikan salah satu daripada dua perkara: sama ada P = NP, yang bermaksud secara keseluruhan, Masalah NP sebagai satu set - termasuk yang kita kenal dan juga yang mungkin kita dapati pada masa akan datang - sebenarnya miliknya P dan dapat diselesaikan dalam masa polinomial; atau P NP dan tidak kira apa algoritma yang kita buat, akan ada asas matematik mengenai kerumitan masa masalah dan lantai itu lebih besar daripada masa polinomial.

Jawapan untuk soalan ini sama ada cukup penting sehingga sesiapa yang mendapat jawapannya akan mendapat hadiah berjuta-juta dolar dari Institut Matematik Clay, belum lagi pemasangan ke dalam panel sains komputer selain John Von Neumann, Alan Turing, Ada Lovelace, dan pencahayaan lain .

Bagi banyak orang, masalah P vs NP kebanyakannya mengenai hakikat bahawa terdapat jurang dalam pemahaman kita mengenai matematik yang perlu diisi. Ahli matematik dan saintis dari semua disiplin menolak pengetahuan, jadi penyelesaian untuk masalah ini adalah yang penting pada prinsipnya. Yang mengatakan, usaha untuk P = NP mempunyai implikasi dunia nyata yang sangat besar jika terbukti bahawa, secara matematik, P = NP. Untuk memahami mengapa, kita perlu membawa dua masalah terakhir yang mengikat semuanya.

NP-Keras dan NP-Lengkap

NP-lengkap adalah kategori khas dari Masalah NP yang mempunyai kerumitan waktu lebih besar daripada waktu polinomial, dapat disahkan dalam waktu polinomial, dan termasuk dalam sekumpulan masalah yang dikenali sebagai NP-keras. NP-keras masalah pada dasarnya adalah masalah yang paling sukar dan sukar Masalah NP, tetapi tidak perlu disahkan dalam masa polinomial.

Menghitung semua kemungkinan subset dari setiap set setiap individu di alam semesta adalah NP-keras masalah. Kami tidak dapat membuktikan bahawa masalah seperti ini tidak dapat diselesaikan dalam masa polinomial, tetapi tidak ada alasan untuk mempercayai bahawa kami akan menemui algoritma itu atau bahkan membina mesin yang cukup kuat untuk menjalankannya dan walaupun seseorang memberi kami jawapan, kami tidak akan malah mula mengetahui cara mengesahkannya.

Yang lain NP-keras masalahnya ialah mengenal pasti pergerakan catur di mana-mana keadaan papan tertentu yang merupakan langkah terbaik yang boleh anda buat. Untuk menentukan ini, anda harus tahu bahawa setiap langkah lain akan membawa kepada hasil yang lebih buruk, dan satu-satunya cara yang kita tahu bagaimana menentukannya adalah dengan mengikuti setiap jalan bercabang dari setiap gerakan, gerakan balas, dan sebagainya yang mungkin. dengan kedudukan papan yang diberi. Sebaik sahaja anda sampai pada hasil akhir setiap cabang pokok keputusan yang hampir tidak terhingga ini, anda kemudian akan mengambil keputusan terbaik dan mengatakan bahawa ini adalah langkah terbaik yang dapat anda buat.

Meninggalkan fungsi mustahil untuk benar-benar menavigasi pokok ini dalam beberapa miliar bilion tahun akan datang, jika anda memberitahu saya bahawa langkah tertentu benar-benar merupakan langkah terbaik yang boleh anda buat, tidak ada cara untuk saya mengesahkannya dengan cepat. Saya harus menggunakan algoritma permutasi kekuatan kasar yang sama seperti yang anda gunakan untuk meneroka setiap akibat dari setiap pergerakan. Mengesahkan penyelesaian akan mengambil masa yang lama untuk menyelesaikan masalah.

Sekiranya ini terdengar biasa, itu kerana memang begitu. Ini adalah masalah asas yang sama dengan Masalah Penjual Perjalanan, yang bermaksud pada dasarnya adalah mengenai pengoptimuman. Ternyata, ini adalah salah satu ciri yang menentukan NP-lengkap masalah; anda benar-benar hanya berusaha menyelesaikan satu masalah yang mempunyai banyak variasi dan variasi tersebut merangkumi keseluruhan perkara yang kami anggap penting untuk membuat keputusan perniagaan, polisi, atau penyelidikan.

Algoritma untuk Segala-galanya

Inilah sebabnya P = NP penting. Kita tidak dapat mengetahui dengan pasti, tetapi ada sebab untuk mempercayai bahawa jawapan untuk soalan itu berjalan lancar NP-lengkap. Pertama, sebarang algoritma yang mengembalikan penyelesaian kepada NP-lengkap masalah pada masa polinomial dapat diubahsuai untuk menyelesaikan setiap masalah NP-lengkap masalah pada masa polinomial, kerana semuanya adalah masalah yang sama pada intinya.

Bukan hanya itu, tetapi sebahagian daripada definisi a NP-lengkap masalah adalah setiap masalah di NP dapat dikurangkan untuk setiap NP-lengkap masalah, yang bermaksud bahawa algoritma yang menyelesaikan NP-lengkap dalam masa polinomial juga akan menyelesaikan semua NP masalah pada masa polinomial juga; dengan kata lain, menyelesaikan suatu NP-lengkap masalah pada masa polinomial membuktikan P = NP secara lalai dan berkesan menyelesaikan hampir semua masalah pengiraan yang paling sukar di dunia nyata secara semalaman.

Jadi ini pada asasnya menjadikan algoritma yang menyelesaikan NP-lengkap masalah dalam masa polinomial algoritma untuk semuanya. Inilah sebabnya P = NP, persamaan bunyi pelik dan legap ini, sangat menjanjikan jika ia dapat dibuktikan benar dan satu-satunya cara sebenar untuk melakukannya adalah dengan menyelesaikan NP-lengkap masalah pada masa polinomial. Algoritma itu akan menjadi algoritma yang dapat membuka dunia yang sama sekali berbeza dalam sekelip mata. Terdapat banyak kegembiraan di sekitar kemungkinan pengkomputeran kuantum tepat kerana ini mungkin peluang terbaik kita untuk menyelesaikannya NP-lengkap dalam masa polinomial, walaupun masih boleh dilihat atau tidak.

Artikel terakhir dalam siri kami mengenai Algoritma dan Pengiraan, Algoritma Kuantum dan Masa Depan Pengkomputeran Pasca-Klasik, boleh didapati di sini


Tonton videonya: 16. Complexity: P, NP, NP-completeness, Reductions (Januari 2022).