Saya berasumsi bahwa Anda mencari definisi intuitif, karena definisi teknis memerlukan cukup banyak waktu untuk mengerti. Pertama-tama, mari kita ingat konsep awal yang diperlukan untuk memahami definisi tersebut.
- Masalah keputusan : Masalah dengan jawaban ya atau tidak .
Sekarang, mari kita mendefinisikan kelas kompleksitas tersebut .
P
P adalah kelas kompleksitas yang mewakili set semua masalah keputusan yang dapat diselesaikan dalam waktu polinomial .
Artinya, dengan memberikan contoh masalah, jawaban ya atau tidak dapat diputuskan dalam waktu polinomial.
Contoh
Diberikan grafik yang terhubung G
, dapatkah simpulnya diwarnai menggunakan dua warna sehingga tidak ada tepi yang monokromatik?
Algoritma: mulai dengan titik sembarang, warna merah dan semua tetangganya biru dan lanjutkan. Berhenti ketika Anda kehabisan simpul atau Anda dipaksa untuk membuat tepi memiliki kedua titik akhir menjadi warna yang sama.
NP
NP adalah kelas kompleksitas yang mewakili himpunan semua masalah keputusan yang mana contohnya adalah "ya" memiliki bukti yang dapat diverifikasi dalam waktu polinomial.
Ini berarti bahwa jika seseorang memberi kami contoh masalah dan sertifikat (kadang-kadang disebut saksi) untuk jawabannya adalah ya, kita dapat memeriksa apakah itu benar dalam waktu polinomial.
Contoh
Factoration integer ada dalam NP. Ini adalah masalah yang diberikan bilangan bulat n
dan m
, apakah ada bilangan bulat f
dengan 1 < f < m
, sehingga f
membagi n
( f
adalah faktor kecil n
)?
Ini adalah masalah keputusan karena jawabannya ya atau tidak. Jika seseorang tangan kita contoh dari masalah (sehingga mereka menyerahkan kami bilangan bulat n
dan m
) dan integer f
dengan 1 < f < m
, dan klaim bahwa f
adalah faktor dari n
(sertifikat), kita dapat memeriksa jawaban dalam waktu polinomial dengan melakukan pembagian n / f
.
NP-Lengkap
NP-Complete adalah kelas kompleksitas yang mewakili set semua masalah X
dalam NP yang memungkinkan untuk mengurangi masalah NP lainnya Y
menjadi X
waktu polinomial.
Secara intuitif ini berarti bahwa kita dapat menyelesaikan Y
dengan cepat jika kita tahu bagaimana menyelesaikannya X
dengan cepat. Tepatnya, Y
dapat direduksi menjadi X
, jika ada algoritma waktu polinomial f
untuk mengubah contoh y
dari Y
untuk contoh x = f(y)
dari X
dalam waktu polinomial, dengan properti yang jawabannya untuk y
adalah ya, jika dan hanya jika jawaban untuk f(y)
adalah ya.
Contoh
3-SAT
. Ini adalah masalah di mana kita diberi konjungsi (AND) dari disjungsi 3-klausa (OR), pernyataan dari form
(x_v11 OR x_v21 OR x_v31) AND
(x_v12 OR x_v22 OR x_v32) AND
... AND
(x_v1n OR x_v2n OR x_v3n)
di mana masing x_vij
- masing adalah variabel boolean atau negasi dari variabel dari daftar yang telah ditentukan sebelumnya (x_1, x_2, ... x_n)
.
Dapat ditunjukkan bahwa setiap masalah NP dapat dikurangi menjadi 3-SAT . Buktinya teknis dan membutuhkan penggunaan definisi teknis NP ( berdasarkan mesin Turing non-deterministik ). Ini dikenal sebagai teorema Cook .
Apa yang membuat masalah NP-complete penting adalah bahwa jika algoritma waktu polinomial deterministik dapat ditemukan untuk memecahkan salah satu dari mereka, setiap masalah NP dapat dipecahkan dalam waktu polinomial (satu masalah untuk mengatur semuanya).
NP-keras
Secara intuitif, ini adalah masalah yang setidaknya sama sulitnya dengan masalah NP-lengkap . Perhatikan bahwa masalah NP-hard tidak harus di NP , dan tidak harus menjadi masalah keputusan .
Definisi yang tepat di sini adalah bahwa suatu masalah X
adalah NP-hard, jika ada masalah NP-complete Y
, sehingga Y
dapat direduksi ke X
dalam waktu polinomial .
Tetapi karena masalah NP-complete dapat direduksi menjadi masalah NP-complete lainnya dalam waktu polinomial, semua masalah NP-complete dapat dikurangi menjadi masalah NP-hard dalam waktu polinomial. Kemudian, jika ada solusi untuk satu masalah NP-hard dalam waktu polinomial, ada solusi untuk semua masalah NP dalam waktu polinomial.
Contoh
Masalah penghentian adalah masalah NP-hard. Ini adalah masalah yang diberikan program P
dan input I
, apakah akan berhenti? Ini adalah masalah keputusan tetapi tidak dalam NP. Jelas bahwa masalah NP-complete dapat dikurangi untuk yang satu ini. Sebagai contoh lain, setiap masalah NP-lengkap adalah NP-hard.
Masalah NP-complete favorit saya adalah masalah Minesweeper .
P = NP
Ini adalah masalah yang paling terkenal dalam ilmu komputer, dan salah satu pertanyaan paling penting yang menonjol dalam ilmu matematika. Bahkan, tanah liat Institute menawarkan satu juta dolar untuk solusi untuk masalah ini (Stephen Cook Langgan di situs Clay adalah cukup baik).
Jelas bahwa P adalah subset dari NP. Pertanyaan terbuka adalah apakah masalah NP memiliki solusi waktu polinomial deterministik atau tidak. Sebagian besar percaya bahwa mereka tidak. Berikut ini adalah artikel terbaru yang beredar tentang masalah P = NP terbaru (dan pentingnya): Status masalah P versus NP .
Buku terbaik tentang masalah ini adalah Komputer dan Intractability oleh Garey dan Johnson.
I
atasn
variabel, coba semua2^n
tugas yang mungkin untuk variabel dan berhenti jika satu memenuhi proposisi dan jika tidak masukkan loop tak terbatas. Kami melihat bahwa algoritma ini berhenti jika dan hanya jikaI
memuaskan. Jadi, jika kita memiliki algoritma waktu polinomial untuk menyelesaikan masalah penghentian maka kita bisa menyelesaikan SAT dalam waktu polinomial. Oleh karena itu, masalah penghentian adalah NP-hard.Saya sudah melihat-lihat dan melihat banyak penjelasan panjang. Berikut adalah bagan kecil yang mungkin berguna untuk merangkum:
Perhatikan bagaimana kesulitan meningkat dari atas ke bawah: NP apa pun dapat dikurangi menjadi NP-Lengkap , dan NP-Lengkap dapat dikurangi menjadi NP-Hard , semuanya dalam waktu P (polinomial).
Jika Anda dapat memecahkan kelas masalah yang lebih sulit dalam waktu P, itu berarti Anda menemukan cara memecahkan semua masalah yang lebih mudah dalam waktu P (misalnya, membuktikan P = NP, jika Anda mencari cara untuk menyelesaikan masalah NP-Complete di P waktu).
Catatan
Yes
atauNo
entri:Saya juga menemukan diagram ini cukup berguna dalam melihat bagaimana semua jenis ini sesuai satu sama lain (lebih memperhatikan setengah bagian kiri diagram).
sumber
Ini adalah jawaban yang sangat informal untuk pertanyaan yang diajukan.
Bisakah 3233 ditulis sebagai produk dari dua nomor lain yang lebih besar dari 1? Apakah ada cara untuk berjalan di sekitar Tujuh Jembatan Königsberg tanpa mengambil jembatan dua kali? Ini adalah contoh pertanyaan yang memiliki sifat yang sama. Mungkin tidak jelas bagaimana menentukan jawaban secara efisien, tetapi jika jawabannya 'ya', maka ada bukti singkat dan cepat untuk memeriksa. Dalam kasus pertama faktorisasi non-sepele 51; di yang kedua, rute untuk menyusuri jembatan (menyesuaikan kendala).
Masalah keputusan adalah kumpulan pertanyaan dengan jawaban ya atau tidak yang hanya bervariasi dalam satu parameter. Katakan masalahnya COMPOSITE = {"Is
n
composite":n
is integer} atau EULERPATH = {"Apakah grafikG
memiliki jalur Euler?": IsG
a finite graph}.Sekarang, beberapa masalah keputusan memungkinkan algoritma yang efisien, jika tidak jelas. Euler menemukan algoritma yang efisien untuk masalah seperti "Tujuh Jembatan Königsberg" lebih dari 250 tahun yang lalu.
Di sisi lain, untuk banyak masalah keputusan, tidak jelas bagaimana mendapatkan jawabannya - tetapi jika Anda tahu beberapa informasi tambahan, jelas bagaimana cara membuktikan bahwa Anda sudah mendapatkan jawabannya dengan benar. KOMPOSIT adalah seperti ini: Pembagian percobaan adalah algoritma yang jelas, dan lambat: untuk memasukkan angka 10 digit, Anda harus mencoba sekitar 100.000 pembagi yang mungkin. Tetapi jika, misalnya, seseorang mengatakan kepada Anda bahwa 61 adalah pembagi 3233, pembagian panjang sederhana adalah cara yang efisien untuk melihat bahwa mereka benar.
NP kelas kompleksitas adalah kelas masalah keputusan di mana jawaban 'ya' memiliki singkat untuk menyatakan, cepat untuk memeriksa bukti. Suka KOMPOSIT. Satu poin penting adalah bahwa definisi ini tidak mengatakan apa-apa tentang seberapa sulit masalahnya. Jika Anda memiliki cara yang benar dan efisien untuk menyelesaikan masalah keputusan, cukup dengan menuliskan langkah-langkah dalam solusi adalah bukti yang cukup.
Penelitian algoritma berlanjut, dan algoritma pintar baru dibuat setiap saat. Masalah yang Anda mungkin tidak tahu bagaimana menyelesaikannya secara efisien hari ini mungkin ternyata memiliki solusi yang efisien (jika tidak jelas) besok. Bahkan, butuh peneliti hingga tahun 2002 untuk menemukan solusi efisien untuk COMPOSITE! Dengan semua kemajuan ini, orang benar-benar harus bertanya-tanya: Apakah ini sedikit tentang memiliki bukti pendek hanya ilusi? Mungkin setiap masalah keputusan yang cocok dengan bukti yang efisien memiliki solusi yang efisien? Tidak ada yang tahu .
Mungkin kontribusi terbesar untuk bidang ini datang dengan penemuan kelas khusus masalah NP. Dengan bermain-main dengan model sirkuit untuk perhitungan, Stephen Cook menemukan masalah keputusan varietas NP yang terbukti sulit atau lebih sulit daripada setiap masalah NP lainnya. Solusi yang efisien untuk masalah kepuasan boolean dapat digunakan untuk menciptakan solusi yang efisien untuk masalah lain dalam NP. Segera setelah itu, Richard Karp menunjukkan bahwa sejumlah masalah keputusan lain dapat melayani tujuan yang sama. Masalah-masalah ini, dalam arti masalah "paling sulit" di NP, dikenal sebagai masalah NP-lengkap .
Tentu saja, NP hanya merupakan kelas masalah keputusan. Banyak masalah tidak secara alami dinyatakan dengan cara ini: "temukan faktor N", "temukan jalur terpendek dalam grafik G yang mengunjungi setiap titik", "berikan satu set penugasan variabel yang menjadikan ekspresi boolean berikut ini benar". Meskipun seseorang dapat secara informal berbicara tentang beberapa masalah seperti itu "di NP", secara teknis itu tidak masuk akal - mereka bukan masalah keputusan. Beberapa masalah ini bahkan mungkin memiliki kekuatan yang sama dengan masalah NP-complete: solusi yang efisien untuk masalah-masalah (non-keputusan) ini akan mengarah langsung ke solusi yang efisien untuk setiap masalah NP. Masalah seperti ini disebut NP-hard .
sumber
P (Waktu Polinomial): Seperti namanya sendiri, ini adalah masalah yang dapat diselesaikan dalam waktu polinomial.
NP (Waktu Non-deterministik-polinomial): Ini adalah masalah keputusan yang dapat diverifikasi dalam waktu polinomial. Itu berarti, jika saya mengklaim bahwa ada solusi waktu polinomial untuk masalah tertentu, Anda meminta saya untuk membuktikannya. Lalu, saya akan memberi Anda bukti yang dapat Anda verifikasi dengan mudah dalam waktu polinomial. Masalah-masalah semacam ini disebut masalah NP. Perhatikan bahwa, di sini kita tidak berbicara tentang apakah ada solusi waktu polinomial untuk masalah ini atau tidak. Tetapi kita berbicara tentang memverifikasi solusi untuk masalah yang diberikan dalam waktu polinomial.
NP-Hard: Ini setidaknya sekeras masalah tersulit di NP. Jika kita dapat menyelesaikan masalah ini dalam waktu polinomial, kita dapat memecahkan masalah NP yang mungkin ada. Perhatikan bahwa masalah ini tidak selalu merupakan masalah NP. Itu berarti, kami mungkin / mungkin-tidak memverifikasi solusi untuk masalah-masalah ini dalam waktu polinomial.
NP-Complete: Ini adalah masalah yang keduanya NP dan NP-Hard. Itu berarti, jika kita dapat menyelesaikan masalah ini, kita dapat menyelesaikan masalah NP lainnya dan solusi untuk masalah ini dapat diverifikasi dalam waktu polinomial.
sumber
Selain jawaban hebat lainnya, berikut adalah skema tipikal yang digunakan orang untuk menunjukkan perbedaan antara NP, NP-Complete, dan NP-Hard:
sumber
Cara termudah untuk menjelaskan Pv. NP dan semacamnya tanpa masuk ke teknis adalah untuk membandingkan "masalah kata" dengan "masalah pilihan ganda".
Ketika Anda mencoba memecahkan "masalah kata", Anda harus menemukan solusinya dari awal. Ketika Anda mencoba untuk memecahkan "masalah pilihan ganda" Anda punya pilihan: pecahkanlah seperti "masalah kata", atau coba pasang setiap jawaban yang diberikan kepada Anda, dan pilih jawaban yang cocok.
Sering terjadi bahwa "masalah pilihan ganda" jauh lebih mudah daripada "masalah kata" yang sesuai: mengganti jawaban kandidat dan memeriksa apakah cocok mungkin memerlukan usaha yang jauh lebih sedikit daripada menemukan jawaban yang tepat dari awal.
Sekarang, jika kita akan menyetujui upaya yang memakan waktu polinomial "mudah" maka kelas P akan terdiri dari "masalah kata mudah", dan kelas NP akan terdiri dari "masalah pilihan ganda yang mudah".
Inti dari Pv. NP adalah pertanyaan: "Apakah ada masalah pilihan ganda yang mudah yang tidak semudah masalah kata"? Yaitu, apakah ada masalah yang mudah untuk memverifikasi validitas jawaban yang diberikan tetapi menemukan bahwa jawaban dari awal sulit?
Sekarang kita mengerti secara intuitif apa itu NP, kita harus menantang intuisi kita. Ternyata ada "masalah pilihan ganda" yang, dalam beberapa hal, adalah yang paling sulit dari semuanya: jika seseorang akan menemukan solusi untuk salah satu dari masalah "yang paling sulit dari semuanya" itu, seseorang akan dapat menemukan solusi untuk SEMUA Masalah NP! Ketika Cook menemukan ini 40 tahun yang lalu, itu mengejutkan. Masalah "paling sulit dari semuanya" ini dikenal sebagai NP-hard. Jika Anda menemukan "solusi masalah kata" untuk salah satu dari mereka, Anda akan secara otomatis menemukan "solusi masalah kata" untuk masing-masing dan setiap "masalah pilihan ganda yang mudah"!
Akhirnya, masalah NP-lengkap adalah mereka yang secara bersamaan NP dan NP-keras. Mengikuti analogi kami, mereka secara simultan "semudah masalah pilihan ganda" dan "yang paling sulit di antara mereka semua sebagai masalah kata".
sumber
Masalah NP-complete adalah masalah yang keduanya NP-Hard dan di kelas kompleksitas NP. Oleh karena itu, untuk menunjukkan bahwa masalah yang diberikan adalah NP-complete, Anda harus menunjukkan bahwa masalahnya adalah NP dan hard-NP.
Masalah yang ada di kelas kompleksitas NP dapat diselesaikan secara non-deterministik dalam waktu polinomial dan solusi yang mungkin (yaitu, sertifikat) untuk masalah dalam NP dapat diverifikasi untuk kebenaran dalam waktu polinomial.
Contoh solusi non-deterministik untuk masalah k-clique akan menjadi seperti:
1) secara acak memilih k node dari grafik
2) memverifikasi bahwa k node ini membentuk sebuah klik.
Strategi di atas adalah polinomial dalam ukuran grafik input dan oleh karena itu masalah k-klik di NP.
Perhatikan bahwa semua masalah yang dapat dipecahkan secara deterministik dalam waktu polinomial juga dalam NP.
Menunjukkan bahwa suatu masalah adalah NP-hard biasanya melibatkan pengurangan dari beberapa masalah NP-hard lain untuk masalah Anda menggunakan pemetaan waktu polinomial: http://en.wikipedia.org/wiki/Reduction_(complexity)
sumber
Saya pikir kita bisa menjawabnya dengan lebih ringkas. Saya menjawab pertanyaan terkait , dan menyalin jawaban saya dari sana
Tapi pertama-tama, masalah NP-hard adalah masalah yang kami tidak dapat membuktikan bahwa ada solusi waktu polinomial. Kekerasan NP dari beberapa "problem-P" biasanya dibuktikan dengan mengubah masalah NP-hard yang sudah terbukti menjadi "problem-P" dalam waktu polinomial.
sumber
Ada jawaban yang sangat bagus untuk pertanyaan khusus ini, jadi tidak ada gunanya menulis penjelasan saya sendiri. Jadi saya akan mencoba berkontribusi dengan sumber yang bagus tentang berbagai kelas kompleksitas komputasi.
Untuk seseorang yang berpikir bahwa kompleksitas komputasi hanya tentang P dan NP, berikut adalah sumber daya yang paling lengkap tentang berbagai masalah kompleksitas komputasi. Terlepas dari masalah yang ditanyakan oleh OP, itu terdaftar sekitar 500 kelas yang berbeda dari masalah komputasi dengan deskripsi yang bagus dan juga daftar makalah penelitian mendasar yang menggambarkan kelas.
sumber
Seperti yang saya pahami, masalah np-hard tidak "lebih keras" dari masalah np-complete . Faktanya, menurut definisi, setiap masalah np-complete adalah:
sumber
Temukan beberapa definisi menarik:
sumber