Application
Application (aplikasi) adalah perangkat lunak yang dibuat dengan algoritma untuk mengerjakan tugas-tugas tertentu.
Pada 1930-an, Alan Turing menunjukkan ada tugas-tugas dasar yang tidak mungkin dicapai dengan cara algoritmik. Dalam istilah modern, yang ditunjukkannya adalah bahwa tidak ada program komputer umum yang menjawab ya atau tidak terhadap pertanyaan apakah program komputer lain pada akhirnya akan berhenti ketika dijalankan.
Kegagalan yang luar biasa dari Masalah Pemutusan ini mengandung kehalusan yang lebih membingungkan. Meskipun kita tidak memiliki cara untuk mengetahui terlebih dahulu apakah suatu program akan berhenti, pada prinsipnya ada cara yang jelas untuk menunjukkan bahwa itu berhenti jika itu adalah program penghentian: jalankan, tunggu, dan saksikan ia berhenti!
Dengan kata lain, Turing menunjukkan bahwa, pada tingkat terluas, memutuskan apakah pernyataan itu benar secara komputasi lebih sulit daripada menunjukkan bahwa itu benar ketika itu.
- Pertanyaan efisiensi
Tetapi sementara Masalah Turing Turing dapat dibuktikan tidak mungkin dalam beberapa garis magis, batas antara "efisien" dan "tidak efisien" tampaknya jauh lebih sulit dipahami. P versus NP adalah yang paling terkenal dari sejumlah besar pertanyaan yang belum terselesaikan yang muncul dari pandangan modern terhadap pertanyaan Turing.
- Jadi apa hal NP ini?
NP kelas berhubungan dengan masalah yang, ketika jawabannya adalah "ya", ada demonstrasi yang efisien bahwa jawabannya adalah ya ("N" adalah singkatan dari "nondeterministic", tetapi deskripsi yang diambil di sini lebih intuitif). P versus NP hanya menanyakan apakah kedua kelas masalah komputasi ini sama.
Ini hanya masalah "memutuskan versus mendemonstrasikan" dalam Masalah Puting asli Turing, tetapi dengan kondisi efisiensi tambahan.
- Teka-teki
Bahkan yang lebih jernih adalah Sudoku: sekali lagi ini adalah tantangan sejati untuk dipecahkan, tetapi memeriksa solusi yang ada untuk kebenarannya begitu rutin sehingga tidak memiliki nilai hiburan.
Kemungkinan P = NP seperti menemukan bahwa bagian "menemukan" dari teka-teki ini hanya memiliki kesulitan yang sama dengan bagian "memeriksa". Itu sepertinya sulit dipercaya, tapi sebenarnya kita tidak tahu pasti.
Intuisi yang sama ini meliputi banyak sekali tugas komputasi penting yang saat ini kita tidak memiliki algoritma yang efisien. Salah satu fitur yang sangat menggoda adalah bahwa, lebih sering daripada tidak, masalah-masalah ini dapat ditunjukkan secara maksimal sulit di antara masalah NP.
Masalah yang disebut " NP-complete " ini adalah kasus uji untuk P versus NP: jika salah satu dari mereka memiliki solusi algoritme yang efisien maka mereka semua melakukannya (dan pemeriksaan yang efisien tidak lebih sulit daripada penemuan yang efisien).
Tetapi jika bahkan hanya satu yang dapat terbukti tidak memiliki solusi yang efisien, maka P tidak sama dengan NP (dan temuan yang efisien sebenarnya, secara umum, lebih sulit daripada pengecekan yang efisien).
Berikut adalah beberapa contoh klasik dari masalah NP-complete.
- Partisi (dilema alien pick-pocket)
- Penjadwalan
- Travelling Salesman
- Bukti singkat
Dalam setiap kasus, kita tahu tidak ada algoritma pasti yang efisien, dan tidak adanya algoritma seperti itu setara dengan membuktikan P tidak sama dengan NP.
Jadi, apakah kita sudah dekat dengan solusi? Tampaknya yang terbaik yang kita tahu adalah bahwa kita tidak tahu banyak! Dapat diperdebatkan, kemajuan paling substansial dalam saga P versus NP secara aneh negatif: mereka kebanyakan menunjukkan bahwa kita tidak mungkin berharap untuk menyelesaikan P sebagai berbeda dengan NP dengan teknik yang sudah dikenal.
Kita tahu pendekatan Turing tidak bisa bekerja. Pada tahun 2007, Alexander Razborov dan Steven Rudich dianugerahi Hadiah Gödel (sering disebut-sebut sebagai Hadiah Nobel Ilmu Komputer) untuk karya mereka yang menunjukkan bahwa tidak ada "bukti alami" yang dapat membuktikan P tidak setara dengan NP.
Tentu saja, kita akan terus mencari!
P adalah polinomial dan NP adalah polinomial non-deterministik. Dalam istilah yang lebih sederhana, P berarti masalah yang mudah dipecahkan oleh komputer, dan NP berarti masalah yang tidak mudah dipecahkan komputer tetapi mudah diperiksa.
Contohnya adalah menemukan bilangan prima, Mudah untuk memeriksa apakah bilangan tersebut prima atau tidak, tetapi sangat sulit untuk menentukan angka-angka itu karena sampai saat ini distribusinya masih berupa dugaan saja (Hipotesa Riemann).
Untuk beberapa pertanyaan praktis yang menarik dari jenis ini, kita tidak memiliki cara untuk menemukan jawaban dengan cepat, tetapi jika kita diberikan jawaban, adalah mungkin untuk memeriksa itu dan memverifikasi jawabannya dengan cepat.
Dengan cara ini, masalah NP dapat dianggap sebagai seperti teka-teki: mungkin sulit untuk menemukan jawaban atas sebuah teka-teki, tetapi begitu seseorang mendengar jawabannya, jawabannya tampak jelas.
Dalam perbandingan (analogi) ini, pertanyaan dasarnya adalah: apakah teka-teki benar-benar sekeras yang kita pikirkan, atau apakah kita kehilangan sesuatu?
Masalah ini pertama kali diangkat oleh ahli matematika Austria-Amerika Kurt Gödel yang membingungkan. Kemudiam dirumuskan oleh Stephen Cook pada tahun 1971.
Setelan distribusi yang seragam atas input ukuran mungkin tidak memodelkan realitas dengan baik, atau perlu didefinisikan. Misalnya, pengurutan cepat diketahui memiliki kompleksitas rata-rata yang baik tetapi berkinerja sangat buruk pada daftar yang sudah disortir.
Namun, dalam praktiknya kita sering mengerjakan daftar yang disortir. Jadi hal ini tidak hanya merupakan pertanyaan yang sangat teoretis dalam ilmu komputer dan matematika, tetapi juga memiliki implikasi besar terhadap dunia nyata.
Masalah ini kemudian dianggap oleh banyak orang sebagai masalah terbuka terpenting dalam bidang ilmu komputer.
Resolusi ini dapat merevolusi dunia.
Beberapa algoritma diketahui memiliki kompleksitas rata-rata berbeda dalam waktu kasus-terburuknya yang dibatasi oleh fungsi polinomial jika melebihi ukuran input waktu yang dibutuhkan Mesin Turing untuk berhenti.
Pernyataan terperinci masalah P versus NP diperkenalkan pada tahun 1971 oleh Stephen Cook dalam makalah seminarnya “Kompleksitas prosedur pembuktian teorema”:
Berikut ini akan diuraikan definisi dan hasil utama P = NP. Detilnya Anda bisa ikuti pada artikel yang berjudul: P versus NP: A Crucial Open Problem.
- Simbol "P"
P mewakili sekumpulan masalah keputusan yang dapat diselesaikan dengan mesin Turing deterministik dengan kompleksitas waktu polinomial dalam kasus terburuk.
- Masalah Keputusan
Misalnya, masalah "Apakah elemen-elemen array berbeda?"
Ini adalah masalah keputusan yang memperhitungkan array sebagai input, dan yang jawabannya adalah ya atau tidak. Sederhana bukan?
- Mesin Turing Deterministik
Meskipun tidak semua algoritma sesuai dengan mesin Turing, sebagian besar algoritma yang kita gunakan atau tulis di komputer sesuai dengan definisi mesin Turing.
Mesin Turing dapat dipahami sebagai satu set keadaan yang memungkinkan transisi antar kondisi sesuai dengan operasi dasar.
Pada setiap langkah algoritma, tergantung pada kondisi saat ini dan pada input yang sedang dibaca oleh mesin, transisi menuju status berikutnya diambil.
Algoritma pertemanan Sheldon berikut dapat digambarkan sebagai mesin Turing, di mana area biru adalah status dan transisi diwakili oleh panah:
Ada beberapa kondisi spesifik. Salah satunya adalah kondisi awal. Dalam algoritma Sheldon, keadaan awal adalah keadaan di kiri atas yang disebut "Panggilan Telepon". Kemudian, ada negara yang dikenal sebagai negara bagian terakhir atau negara penerima.
Pada contoh ini, algoritma selesai. Hasil algoritma ditentukan oleh kondisi akhir yang akhirnya akan tercapai. Hasil ini merujuk pada status "Mulailah Frienship" dan "Partake in Interest" dalam masalah keputusan.
Pada beberapa tempat akan merujuk ke jawaban "benar", dan yang lain untuk jawaban "salah".
Akankah transisi selalu mengarah ke kondisi akhir? Tidak. Lihatlah algoritma persahabatan Sheldon misalnya. Jika tidak memiliki jumlah loop, itu mungkin tetap dalam loop ini tanpa batas. Faktanya, mengetahui apakah suatu algoritma akan mencapai kondisi akhir adalah masalah yang sulit. Memang, pada akhir 1930-an, Alan Turing, pendiri ilmu komputer modern, telah membuktikan bahwa tidak ada mesin Turing yang, mengingat mesin Turing dan input, dapat menentukan apakah mesin Turing akan selesai dengan input. Secara setara, kita mengatakan bahwa menentukan apakah mesin Turing akan berhenti dengan input apa pun tidak dapat ditentukan. Masalah ini dikenal sebagai masalah penghentian dan merupakan kasus teorema Rice. Teorema ini mengatakan bahwa masalah non-sepele tidak dapat diputuskan. Tapi ini semakin rumit dan saya tidak akan memikirkan itu.
Saya tidak benar-benar melihat hubungan antara mesin Turing dan komputer ... Komputer dapat dimodelkan dengan mesin Turing. Memang, setiap keadaan dari seluruh memori komputer dapat dimodelkan dengan keadaan di mesin Turing. Sekarang, pada setiap langkah algoritma yang dijalankan pada komputer, memori dan input dibaca, dan, berdasarkan instruksi yang diberikan, keputusan untuk menimpa memori diambil. Ini mengarah ke keadaan memori yang baru. Dengan demikian, keputusan untuk menimpa sesuai dengan transisi.
Ini sedikit tentang mesin Turing. Seperti Alan Turing membuktikannya, ada mesin Turing, yang disebut mesin Turing universal, sehingga, mesin Turing lainnya dapat disimulasikan oleh mesin Turing universal, dengan menulis instruksi pada input. Untuk komputer, ini sesuai dengan mengatakan bahwa bahasa pemrograman seperti C ++ atau Java adalah mesin Turing universal. Anda dapat menulis instruksi, menambahkan input, dan memberikannya ke bahasa-bahasa tersebut untuk menjalankan algoritma apa pun.
Fakta penting adalah bahwa komputer dapat dipahami sebagai mesin Turing. Jadi, algoritma yang biasanya kita tulis termasuk dalam definisi P.
Saya kira saya mendapatkan apa itu mesin Turing ... Sekarang, apa kompleksitas waktu polinomialnya? Nah, untuk itu saya pertama-tama perlu berbicara tentang ukuran input dan waktu yang dibutuhkan untuk menyelesaikan suatu algoritma ...
Kedua konsep itu tampaknya cukup sederhana ... Maksud saya, ukuran input adalah jumlah byte, bukan? Ya, ukuran input sering diukur dalam byte. Tetapi dalam banyak kasus, kita lebih suka menggambarkan ukuran input dengan angka yang sebanding dengan ukuran dalam byte. Misalnya, dalam kasus array, ukuran input dapat dianggap sebagai jumlah elemen array. Entah representasi setara dengan definisi yang akan kita lihat.
Dan saya kira waktunya tidak diukur dalam hitungan detik ... Masalah dengan mengukur waktu dalam hitungan detik adalah waktu yang dibutuhkan suatu algoritma untuk menyelesaikannya sangat tergantung pada kekuatan prosesor Anda. Dan itu tidak semua, seperti komputer sekarang muli-tugas segalanya, jika Anda menjalankan suatu algoritma dengan input yang sama dua kali pada komputer yang sama, mungkin tidak akan membutuhkan jumlah detik yang sama untuk menyelesaikannya. Itu sebabnya, ketika memungkinkan, kita lebih suka mengukur adalah jumlah operasi dasar (tes, penambahan ...) yang dilakukan oleh komputer. Waktu lain ini hampir sebanding dengan waktu aktual dalam detik, dan setara dengan definisi yang akan kita lihat.
OK, jadi sekarang Anda dapat memberi tahu kita apa arti kompleksitas waktu polinomial ... Iya! Mesin Turing memiliki kompleksitas waktu polinomial jika ada polinomial sedemikian rupa sehingga untuk setiap input ukuran, waktu yang dibutuhkan mesin Turing untuk berhenti kurang dari . Dalam hal ini, kita akan tahu pasti bahwa algoritma akan selesai dalam jumlah waktu yang wajar untuk input apa pun. Ini sesuai dengan mengatakan bahwa bahkan dalam kasus terburuk, waktu kompleksitas adalah polinomial dalam ukuran input.
Saya kira Anda sekarang memiliki semua informasi untuk memahami masalah keputusan apa yang dapat diselesaikan oleh mesin Turing dengan kompleksitas waktu polinomial dalam kasus terburuk.
Saya kira ... Bisakah Anda memberi contoh? Hanya untuk memastikan saya mendapatkannya ... Tentu! Alih-alih meminta orang lain untuk membuat saran satu per satu, Sheldon dapat meminta orang lain untuk memberikan daftar saran. Namun, Sheldon agak gila, jadi dia akan memastikan bahwa orang lain itu tidak mengacaukannya. Misalnya, ia mungkin ingin memastikan bahwa semua saran berbeda satu sama lain.
Masalah pengujian apakah elemen daftar semuanya berbeda ada di P. Pertama, ini masalah keputusan. Kemudian, mari pertimbangkan algoritma berikut. Kita akan mempertimbangkan setiap pasangan elemen dari daftar. Jika dua elemen dari setiap pasangan berbeda satu sama lain, maka jawabannya akan "benar".
Bagaimana kita bisa mendaftar semua pasangan daftar? Nah, cara biasa adalah memberi perintah kepada elemen-elemen daftar. Kemudian, kita akan mempertimbangkan kecocokan setiap elemen dengan setiap pengikutnya di daftar. Berikut ini adalah representasi grafis dari itu, di mana setiap baris sesuai dengan pasangan.
Algoritma ini menjawab pertanyaan. Selain itu, jika ada elemen dalam daftar, karena ada pasang daftar, kita harus melakukan paling banyak iterasi, dengan satu operasi dasar per iterasi (tes apakah yang pertama berbeda dari yang terakhir). Dengan demikian, jumlah operasinya kurang dari. Dengan demikian, algoritma ini polinomial. Dengan demikian, masalah keputusan ini dapat diselesaikan dengan mesin Turing dalam waktu polinomial dalam kasus terburuk: Ada dalam P.
- NP
Saya kira NP berarti "Non-polinomial", bukan? Tidak! Meskipun "N" berarti "Non" dan "P" untuk "Polinomial", "NP" adalah Polinomial Non-deterministik. Ini adalah serangkaian masalah keputusan yang, jika jawabannya benar, dapat diselesaikan dengan mesin Turing non-deterministik dalam waktu polinomial dalam kasus terburuk.
Apa itu mesin Turing non-deterministik?
Mesin Turing non-deterministik sangat mirip dengan mesin Turing deterministik, tetapi memiliki beberapa perbedaan. Terutama, ini memungkinkan, diberikan keadaan dan input, transisi menuju beberapa keadaan atau tidak sama sekali. Jika ada jalur yang menggunakan transisi ini dari kondisi awal ke kondisi akhir, maka mesin mengembalikan "true". Karena itu, mesin Turing non-deterministik sangat berbeda dari mesin Turing. Jawabannya tidak dibaca pada keadaan akhir tercapai karena mungkin ada beberapa keadaan akhir yang dapat dicapai. Jika jawaban ditemukan, itu pasti "benar".
Berbeda dengan mesin Turing deterministik yang dapat digambarkan sebagai jalur dari kondisi awal ke kondisi akhir melalui kondisi perantara menggunakan transisi, mesin Turing non-deterministik tidak dapat digambarkan sebagai jalur. Perlu dipertimbangkan sebagai arborescence, yaitu struktur di mana masing-masing negara memiliki nol, satu atau beberapa "anak" negara (meskipun itu bukan arborescence dalam arti teori grafik karena mungkin ada beberapa jalur dari root ke suatu negara, atau karena ada siklus). Secara ekuivalen, jawaban yang diberikan oleh mesin Turing deterministik adalah "benar" jika ada keadaan akhir di punjung. Gambar berikut adalah representasi dari arborescence dari mesin Turing non-deterministik.
Seperti yang Anda lihat, status dapat memiliki nol, satu atau beberapa transisi. Dalam contoh ini, karena ada keadaan akhir di arborescence, jawabannya adalah "benar".
Mesin non-deterministik dapat dipahami sebagai mesin yang melakukan masing-masing kemungkinan transisi secara bersamaan (dengan, misalnya, bercabang ke mesin lain yang serupa) dan selesai segera setelah salah satu jalur transisi menemukan keadaan akhir. Mereka juga dapat dipahami sebagai penebak keberuntungan yang akan selalu memilih transisi yang tepat, untuk mencapai secepat mungkin keadaan akhir.
Untuk input yang jawabannya "benar", kita dapat mendefinisikan kompleksitas waktu sebagai jumlah transisi dari jalur terpendek menuju kondisi akhir.
Demikian pula dengan P, kita dapat mendefinisikan serangkaian masalah sedemikian sehingga ada mesin Turing non-deterministik yang menjawab dengan benar dengan kompleksitas waktu yang dibatasi oleh fungsi polinomial dari ukuran input. Masalah seperti itu disebut polinomial non-deterministik, yaitu mereka ada di NP.
Waw ... Ini semakin rumit ...
Untungnya, ada tautan menarik antara mesin Turing yang non-deterministik dan deterministik yang dapat membantu kits mengatasi masalah NP. Untuk satu hal, setiap masalah yang dapat diselesaikan dengan mesin Turing non-deterministik dapat diselesaikan dengan mesin Turing. Selain itu, masalah dalam P juga di NP.
Tapi bukan itu saja! Hasil yang paling penting adalah sebagai berikut. Masalahnya adalah NP jika dan hanya jika, untuk input apa pun, ada satu set subproblem keputusan yang terbatas (tetapi berpotensi besar) yang ada di P, sehingga jawaban dari masalah itu benar setiap kali jawaban dari semua subproblem keputusan benar juga .
Bisakah Anda memberi contoh?
Misalkan Sheldon tidak tahu apa kegiatan yang diusulkan. Dia harus pergi ke setiap tempat untuk melihat apa itu dan bagaimana mereka bekerja. Namun dia hanya punya $ 50 untuk taksi. Masalahnya adalah mencari tahu apakah dia akan dapat mengunjungi semua tempat itu.
Gambar sebelumnya menampilkan tempat yang berbeda dan biaya taksi dari masing-masing tempat. Garis merah adalah perjalanan yang memungkinkan bagi Sheldon. Namun, biaya perjalanan merah 3 + 15 + 11 + 23 + 9 + 3 = 64 dolar. Karena Sheldon hanya memiliki $ 50, itu adalah perjalanan yang tidak dapat ia lakukan.
Mengapa NP masalah ini?
Untuk mengetahui apakah dia dapat mengunjungi semua tempat hanya dengan $ 50, dia dapat menguji semua perjalanan yang melewati setiap tempat. Karena ada sejumlah perjalanan terbatas yang melewati setiap tempat, dan sebagai pengujian apakah perjalanan layak dengan $ 50 dapat dilakukan dengan sangat cepat (dengan menambahkan semua biaya taksi dan membandingkan totalnya dengan $ 50 ), masalah ini masuk dalam definisi yang setara masalah NP. Karena itu NP. Bukan berarti ini algoritma yang secara bersamaan mencoba semua perjalanan sebenarnya bukan algoritma yang dilakukan oleh mesin Turing deterministik.
Masalah Sheldon sebenarnya adalah contoh dari masalah keputusan salesman keliling . Masalah ini terdiri lebih umum dari memutuskan apakah ada jalan yang dimulai dan berakhir di rumah, dan melewati semua titik perantara sehingga total biaya perjalanan kurang dari beberapa nilai. Inputnya adalah himpunan titik menengah dan biaya taksi antara dua titik.
Perhatikan bahwa kita dapat memodifikasi algoritme dengan secara berurutan menguji semua perjalanan. Algoritma yang kita peroleh adalah mesin Turing deterministik. Tetapi tidak dalam P. Sebenarnya, jika ada tempat untuk dikunjungi, lalu ada cara bepergian melalui setiap tempat. Dalam contoh kita dengan hanya 5 tempat untuk dikunjungi, algoritme ini membutuhkan 120 tes! Faktanya,tidak dapat dibatasi oleh polinomial apa pun. Ini membuktikan bahwa algoritma tersebut tidak polinomial.
Masalah perutean kendaraan membentuk varian varian kelas besar untuk keliling penjual keliling, dan memiliki banyak aplikasi yang melibatkan jutaan dolar!
Juga perhatikan bahwa dalam banyak artikel, karena penyalahgunaan bahasa, masalah non-keputusan kadang-kadang dikategorikan ke dalam masalah P (atau kelas masalah keputusan lainnya) yang seharusnya menjadi masalah keputusan saja. Ini biasanya berarti bahwa pemecahan masalah dapat dilakukan dalam waktu polinomial (atau dalam waktu yang sama dengan masalah keputusan kelas yang disebutkan). Namun, perlu diketahui bahwa mengenai masalah NP, banyak artikel hanya membuat kesalahan dan menulis misalnya bahwa masalah salesman keliling adalah NP. Karena definisi spesifik NP, hanya masalah keputusan yang benar-benar dapat dianggap NP!
Jadi masalah P = NP terdiri dari ...
Ingin tahu apakah ada masalah dalam NP juga dalam P, yaitu jika masalah NP dapat diselesaikan dalam waktu polinomial dengan mesin Turing deterministik. Seperti yang saya katakan, ini adalah masalah terbuka utama ... dan saya tidak akan menjadi orang dengan jawabannya! Tetapi jika Anda ingin mencobanya, Anda harus tahu tentang konsep seperti NP-hard atau NP-complete.
- NP-hard, NP-complete
Bisakah Anda memberi contoh?
Mari kita tunjukkan bahwa masalah menemukan biaya perjalanan terkecil (sebut saja masalah A) sama sulitnya dengan masalah mengetahui apakah ada kemungkinan perjalanan dengan jumlah uang tertentu (sebut saja masalah B dan perhatikan bahwa itu adalah Sheldon masalah yang kita jelaskan), ketika biaya taksi semuanya bilangan bulat (itu akan benar tanpa asumsi ini, tetapi kita akan menambahkannya untuk mempermudah). Pertama jika kita dapat menemukan A dalam satu operasi dasar, penyelesaian B dapat dilakukan dengan membandingkan jumlah uang dengan biaya perjalanan terkecil. Jadi, A lebih sulit daripada B.
Mari kita sekarang menunjukkan bahwa B lebih sulit daripada A. Kita tahu bahwa biaya perjalanan terkecil adalah antara 0 dan jumlah biaya taksi antara 2 poin. Jadi kita bisa menggunakan pencarian dikotomikuntuk menemukan biaya perjalanan terkecil. Pada setiap langkah, kita tahu bahwa biaya terkecil adalah antara dua nilai. Kita mempertimbangkan cara dua nilai. Kiya menerapkan oracle B untuk mengetahui apakah nilai yang diuji lebih tinggi atau lebih rendah dari biaya terkecil lebih tinggi atau lebih rendah dari nilai yang diuji. Kita kemudian menyesuaikan interval kits di mana kita tahu biaya terkecil. Dengan menerapkan pencarian dikotomik ini, berapa kali kita menggunakan oracle B lebih kecil dari logaritma jumlah biaya taksi antara 2 poin, yaitu tentang jumlah digit yang diperlukan untuk menulis biaya taksi. Akibatnya, jumlah penggunaan B adalah polinomial dalam ukuran input. Oleh karena itu, B lebih sulit daripada A. Seperti yang telah kita tunjukkan bahwa A lebih sulit daripada B, kita sekarang dapat mengatakan bahwa kedua masalah sama sulitnya satu sama lain.
OK saya mendapatkan konsep "lebih keras". Saya kira NP-hard ada hubungannya dengan itu ... Iya! Kita menyebut NP-hard serangkaian masalah (belum tentu masalah keputusan) yang lebih sulit daripada masalah NP apa pun. Cukup aneh, masalah NP-hard belum tentu NP. Ada banyak masalah NP-hard, dan masalah ini pasti ... sulit.
Tapi yang sangat menarik sebenarnya adalah perpotongan dari set masalah NP-hard dan set masalah NP. Set ini disebut NP-complete.
Mengapa masalah NP-complete begitu menarik? Pertama, karena jika Anda dapat menemukan algoritma polinomial untuk menyelesaikan masalah NP-complete, maka Anda akan membuktikannya ! Jelas, ini sebenarnya berlaku untuk masalah NP-hard, karena definisi "lebih keras" yang kita bahas sebelumnya.
Tetapi terutama, karena kita tahu banyak masalah NP-complete, sehingga Anda dapat memilih yang ingin Anda pecahkan. Di antara mereka, mari kita sebutkan masalah kepuasan boolean, masalah keputusan ransel, masalah keputusan penjual keliling, masalah keputusan mewarnai grafik ..
Anda mengatakan bahwa masalah ini P = NP sangat penting ... Mengapa?
Baiklah, jika, maka banyak penelitian dalam optimasi akan sia-sia. Banyak masalah yang kini dihadapi para ilmuwan akan diselesaikan secara instan, seperti pemulihan DNA, perhitungan kesetimbangan Nash, perutean kendaraan ... Tetapi yang lebih penting, beberapa sistem saat ini, terutama dalam kriptografi, dibangun mengingat bahwa, yaitu tidak ada yang bisa memecahkan sistem dalam waktu kurang dari beberapa juta tahun. Misalnya, komunikasi pribadi melalui web termasuk dengan bank Anda menggunakan protokol rahasia. Salah satunya adalah sistem RSA, di mana setiap lembaga memiliki kunci pribadi dan memberikan kunci publik. Anda dapat berbicara dengan lembaga dengan menyandikan pesan Anda dengan kunci publik, tetapi tidak seorang pun kecuali lembaga yang dapat men-decode pesan Anda karena kunci pribadi diperlukan untuk itu. Dan lembaga percaya bahwa tidak ada yang akan bisa menebak kunci pribadi dengan kunci publik ... yang sebenarnya bisa dilakukan, tetapi mungkin perlu beberapa juta tahun. Jika, sebuah algoritma dapat ditemukan untuk menyelesaikannya dalam hitungan hari atau kurang! Saya akan membiarkan Anda membayangkan konsekuensinya ...
Kebanyakan ilmuwan sebenarnya cenderung percaya itu, Yang berarti bahwa masalah NP-hard adalah masalah yang secara intrinsik sulit. Dan akan lebih aman untuk membuat sistem yang mengasumsikan bahwa masalah NP-hard tidak dapat diselesaikan dalam waktu yang wajar. Bagaimanapun, di sini adalah grafik dari apa yang akan menjadi konsekuensi untuk hubungan antara P, NP, NP-lengkap dan NP-keras.
Mari kita simpulkan.
Masalah adalah masalah terbuka mendasar yang sangat sulit dengan banyak implikasi praktis utama. Itu sebabnya mungkin itu masalah utama saat ini. Selain itu, ada banyak interpretasi. Beberapa dari mereka benar-benar mempertimbangkan bahwa cara kita memahami dunia dipahami secara global, termasuk konsep kreativitas, akan sangat terpengaruh. Inilah video yang luar biasa dari Hackerdashery :
Perhatikan bahwa ini bukan satu-satunya masalah terbuka mendasar dalam kompleksitas komputasi. Secara khusus, Masalah lain termasukdimana adalah serangkaian masalah keputusan yang dipecahkan oleh mesin Turing yang tidak deterministik dalam waktu polinomial ketika jawabannya "salah". Ada juga atau dimana mengacu pada algoritma probabilistik dan untuk algoritma kuantum probabilistik.
Banyak ilmuwan cenderung percaya, meskipun argumen utama mereka adalah bahwa, jika P = NP, maka salah satu dari mereka akan menemukan algoritma polinomial untuk menyelesaikan salah satu dari algoritma NP-complete ...
Atau mungkin itu hanya alasan untuk membenarkan bahwa kita tidak tahu jawabannya ... Yang lebih meresahkan lagi, beberapa ilmuwan menyarankan bahwa masalahnya mungkin tidak dapat dipastikan! Ini berarti tidak ada buktinya tidak juga itu .
Penyebabnya adalah matematika tidak cukup berkembang untuk menjawab pertanyaan ini (dan, mungkin, tidak pernah cukup berkembang!).
Namun perlu dicatat bahwa ada masalah yang terbukti lebih sulit daripada masalah P. Juga berkomentar, bahkan jika, mungkin ada algoritma yang dapat memecahkan masalah NP-hard dalam waktu polinomial rata-rata.
;; n-sat-to-clique: formula -> (listof edge)
;; transform an input to n-sat to an input for clique
;; assume the input expression is in CNF, and that
(define (n-sat-to-clique expr)
(let* ([conjuncts (∧-conjuncts expr)]
[columns (map (λ (x) (∨-disjuncts x)) conjuncts)]
[labeled-columns (label-graph columns 1)]
[possible-edges (all-pairs-in-distinct-lists labeled-columns)])
(list->set (filter no-conflict? possible-edges))))
