Koleksi

P vs NP, NP-Complete, dan Algoritma untuk Semuanya

P vs NP, NP-Complete, dan Algoritma untuk Semuanya

Ini adalah artikel keenam dalam seri tujuh bagian tentang Algoritma dan Komputasi, yang membahas bagaimana kita menggunakan bilangan biner sederhana untuk menggerakkan dunia kita. Artikel pertama, Bagaimana Algoritma Menjalankan Dunia Tempat Kita Tinggal, dapat ditemukan di sini.

Ketika kita duduk untuk mencoba dan memecahkan suatu masalah, sangat sedikit dari kita yang mencoba mencari tahu jenis masalah apa yang sedang kita coba selesaikan. Dalam hampir setiap kasus, jawaban atas pertanyaan itu adalah latihan yang menarik dan bahkan dapat membantu Anda memecahkan masalah dalam beberapa kasus, tetapi tidak banyak yang lainnya. Tetapi situasinya sangat berbeda dengan sesuatu seperti Travelling Salesman Problem, itulah sebabnya mengapa hal ini menjadi subjek studi dan penelitian oleh para ilmuwan komputer teoritis dan ahli matematika. Memiliki segala sesuatu hubungannya dengan klasifikasi sebagai masalah.

Klasifikasi Masalah: P Vs NP

Masalah yang kita ketahui algoritme efisiennya yang mampu menghasilkan solusi dalam waktu polinomial diklasifikasikan sebagai Masalah P.P. cara waktu polinomial, dalam hal ini. Ini jelas merupakan bagian pertama dari masalah yang dapat kami klasifikasikan: dari semua masalah di luar sana, setidaknya kami berhasil menyelesaikannya di sini. Hal-hal seperti menyortir daftar, menyeimbangkan pohon, mengenkripsi data adalah semua masalah yang kami miliki dengan algoritme yang efisien dan jadi milik subset P..

Kemudian, kami menemukan bagian lain dari masalah itu P. itu sendiri adalah bagian dari, Masalah NP. Itu NP berdiri untuk waktu polinomial nondeterministik, tetapi untuk tujuan kami, Anda tidak perlu tahu terlalu banyak tentang apa artinya kecuali bagian dari ilmu komputer era Turing yang mendasari setiap komputer modern. Yang perlu Anda ketahui adalah itu Masalah NP tidak memiliki algoritme yang diketahui yang dapat menghasilkan hasil dalam waktu polinomial.

Namun, jika Anda diberi solusi untuk file Masalah NP, memverifikasi kebenarannya mudah dan dapat dilakukan di waktu polinomial atau kurang. Kami menggunakan fakta ini setiap kali kami membuka kunci iPhone kami atau mengirim pesan melalui WhatsApp. Ternyata, Masalah NP sempurna untuk enkripsi; hanya ada satu cara untuk menyelesaikan masalah yang membuka kunci enkripsi dengan cepat, Anda harus memiliki jawabannya sebelumnya.

TERKAIT: 7 ALGORITMA PENTING YANG MENJALANKAN DUNIA

Biasanya, kami menyukai enkripsi, dan kami senang enkripsi itu aman untuk saat ini, tetapi ada banyak masalah di dalamnya NP bahwa kita benar-benar membutuhkan algoritme yang efisien. Terlepas dari upaya terbaik dari beberapa orang yang sangat pintar, bagaimanapun, hanya ada sedikit kemajuan dalam menyelesaikan semua kecuali sangat sedikit Masalah NP yang kami ketahui. Ini telah menghasilkan salah satu masalah matematika dan komputasi besar yang belum terpecahkan selama 50 tahun terakhir: P vs NP, disebut juga P = NP.

Apa yang diminta persamaan ini adalah dapat diberikan Masalah NP diselesaikan dalam waktu polinomial, sehingga membuat Masalah NP Betulkah Masalah P. yang hanya perlu diselesaikan dengan baik, atau memang ada Masalah NP yang tidak ada solusi yang dapat ditemukan dalam waktu polinomial dan dengan demikian tetap praktis tidak dapat dipecahkan, apa pun algoritme yang kami kembangkan?

Saat melihat dua rangkaian masalah ini, P vs NP, tujuannya adalah untuk membuktikan salah satu dari dua hal: baik P = NP, artinya secara keseluruhan, Masalah NP sebagai satu set — termasuk yang kita ketahui serta yang mungkin kita temukan di masa depan — sebenarnya milik P. dan dapat diselesaikan dalam waktu polinomial; atau P. NP dan bahwa apa pun algoritme yang kami hasilkan, akan ada dasar matematika pada kompleksitas waktu masalah dan floor tersebut lebih besar dari waktu polinomial.

Jawaban atas pertanyaan ini cukup penting sehingga siapa pun yang menemukan jawabannya akan mendapatkan hadiah jutaan dolar dari Clay Mathematics Institute, belum lagi pemasangan ke jajaran ilmu komputer selain John Von Neumann, Alan Turing, Ada Lovelace, dan tokoh-tokoh terkenal lainnya. .

Bagi banyak orang, masalah P vs NP sebagian besar tentang fakta bahwa ada kesenjangan dalam pemahaman kita tentang matematika yang perlu diisi. Matematikawan dan ilmuwan dari semua disiplin ilmu membenci kekosongan pengetahuan, jadi solusi untuk masalah ini adalah yang penting secara prinsip. Konon, pengejaran P = NP memiliki implikasi dunia nyata yang sangat besar jika terbukti bahwa, secara matematis, P = NP. Untuk memahami alasannya, kita perlu memasukkan dua rangkaian masalah terakhir yang mengikat semuanya.

NP-Hard dan NP-Complete

NP-complete adalah kategori khusus dari Masalah NP yang memiliki kompleksitas waktu lebih besar dari waktu polinomial, dapat diverifikasi dalam waktu polinomial, dan termasuk dalam kumpulan masalah yang dikenal sebagai NP-hard. NP-hard Masalah pada dasarnya adalah yang paling tidak sekeras yang tersulit Masalah NP, tetapi tidak perlu diverifikasi dalam waktu polinomial.

Menghitung semua subset yang mungkin dari himpunan setiap atom di alam semesta adalah NP-hard masalah. Kami tidak dapat membuktikan bahwa masalah seperti itu tidak dapat diselesaikan dalam waktu polinomial, tetapi tidak ada alasan untuk percaya bahwa kami akan menemukan algoritme tersebut atau bahkan membuat mesin yang cukup kuat untuk menjalankannya dan bahkan jika seseorang memberi kami jawaban, kami tidak akan bahkan mulai mengetahui bagaimana cara memverifikasinya.

Lain NP-hard Masalahnya adalah mengidentifikasi gerakan catur dalam keadaan papan tertentu yang merupakan langkah terbaik mutlak yang dapat Anda lakukan. Untuk menentukan ini, Anda harus tahu bahwa setiap gerakan lain akan menghasilkan hasil yang lebih buruk, dan satu-satunya cara yang kami ketahui cara menentukannya adalah dengan mengikuti setiap jalur percabangan dari setiap gerakan, gerakan balasan, dan sebagainya yang memungkinkan. dengan posisi papan yang diberikan. Begitu Anda sampai pada hasil akhir dari setiap cabang dari pohon keputusan yang praktis tak terbatas ini, Anda kemudian akan mengambil hasil terbaik dan mengatakan bahwa ini adalah langkah terbaik yang dapat Anda lakukan.

Mengesampingkan fungsi yang mustahil untuk benar-benar menavigasi pohon ini dalam beberapa miliar miliar tahun mendatang, jika Anda memberi tahu saya bahwa gerakan tertentu benar-benar merupakan gerakan terbaik yang dapat Anda lakukan, tidak ada cara bagi saya untuk memverifikasi ini dengan cepat. Saya harus menggunakan algoritma permutasi kekerasan yang sama persis dengan yang baru saja Anda gunakan untuk menjelajahi setiap konsekuensi dari setiap gerakan. Memverifikasi solusi akan memakan waktu selama yang dibutuhkan untuk menyelesaikan masalah.

Jika ini terdengar familier, itu karena memang begitu. Ini adalah masalah dasar yang sama dengan Masalah Penjual Bepergian, artinya ini pada dasarnya tentang pengoptimalan. Ternyata, ini adalah salah satu karakteristik yang menentukan NP-complete masalah; Anda benar-benar hanya mencoba menyelesaikan satu masalah yang memiliki variasi yang tak terhitung jumlahnya dan variasi tersebut mencakup keseluruhan dari apa yang kami anggap penting untuk pengambilan keputusan bisnis, kebijakan, atau penelitian.

Algoritma untuk Segalanya

Ini sebabnya P = NP masalah. Kami tidak dapat mengetahui secara pasti, tetapi ada banyak alasan untuk percaya bahwa jawaban atas pertanyaan itu berjalan lancar NP-complete. Pertama, algoritme apa pun yang mengembalikan solusi ke file NP-complete masalah dalam waktu polinom dapat dimodifikasi untuk menyelesaikan setiap masalah NP-complete masalah dalam waktu polinomial, karena mereka semua adalah masalah yang sama pada intinya.

Bukan hanya itu, tetapi bagian dari definisi file NP-complete masalah adalah setiap masalah yang ada NP dapat direduksi menjadi setiap NP-complete masalah, yang berarti bahwa algoritme yang memecahkan NP-complete dalam waktu polinom juga akan menyelesaikan semua NP masalah dalam waktu polinomial juga; dengan kata lain, memecahkan file NP-complete masalah dalam waktu polinom terbukti P = NP secara default dan secara efektif memecahkan hampir semua masalah komputasi tersulit di dunia nyata dalam semalam.

Jadi ini pada dasarnya membuat algoritme yang memecahkan file NP-complete masalah dalam waktu polinomial algoritma untuk semuanya. Ini sebabnya P = NP, persamaan yang terdengar aneh dan tidak jelas ini, memiliki begitu banyak janji jika dapat dibuktikan benar dan satu-satunya cara nyata untuk melakukannya adalah dengan NP-complete masalah dalam waktu polinomial. Algoritme itu akan menjadi algoritme yang dapat membuka dunia yang sama sekali berbeda dalam sekejap. Ada banyak kegembiraan di sekitar kemungkinan komputasi kuantum justru karena itu mungkin kesempatan terbaik kita untuk menyelesaikannya NP-complete dalam waktu polinomial, meskipun masih bisa dilihat atau tidak.

Artikel terakhir dalam seri kami tentang Algoritma dan Komputasi, Algoritma Kuantum dan Masa Depan Komputasi Pascaklasik, dapat ditemukan di sini


Tonton videonya: P vs NP. What are NP-Complete and NP-Hard Problems? (Oktober 2021).