Pertanyaan Apa perbedaan antara NP, NP-Complete dan NP-Hard?


Apa perbedaan antara NP, NP-Lengkap dan NP-Hard?

Saya menyadari banyak sumber daya di seluruh web. Saya ingin membaca penjelasan Anda, dan alasannya adalah mereka mungkin berbeda maka apa yang ada di luar sana, atau di luar sana dan saya tidak menyadarinya.


906
2017-12-07 01:11


asal


Jawaban:


Saya berasumsi bahwa Anda mencari definisi intuitif, karena definisi teknis membutuhkan waktu yang cukup lama untuk dipahami. Pertama-tama, mari kita ingat konsep awal yang dibutuhkan untuk memahami definisi-definisi tersebut.

  • Masalah keputusan: Masalah dengan iya nih atau tidak menjawab.

Sekarang, mari kita mendefinisikannya kelas kompleksitas.

P

P adalah kelas kompleksitas yang mewakili himpunan semua masalah keputusan yang dapat diselesaikan dalam waktu polinomial.

Artinya, diberi contoh masalah, jawabannya ya atau tidak dapat diputuskan dalam waktu polinomial.

Contoh

Diberikan grafik terhubung G, dapat verteksnya diwarnai menggunakan dua warna sehingga tidak ada tepi monokromatik?

Algoritma: mulai dengan titik yang berubah-ubah, warnai merah dan semua tetangganya berwarna biru dan lanjutkan. Berhenti ketika Anda kehabisan simpul atau Anda dipaksa untuk membuat tepi memiliki kedua titik ujungnya menjadi warna yang sama.


NP

NP adalah kelas kompleksitas yang mewakili himpunan semua masalah keputusan di mana contoh di mana jawabannya adalah "ya" memiliki bukti yang dapat diverifikasi dalam waktu polinomial.

Ini berarti bahwa jika seseorang memberi kita contoh masalah dan sertifikat (kadang-kadang disebut saksi) untuk jawabannya adalah ya, kita dapat memeriksa bahwa itu benar dalam waktu polinomial.

Contoh

Factorasi bilangan bulat ada di NP. Ini adalah masalah yang diberikan bilangan bulat n dan m, apakah ada bilangan bulat f dengan 1 < f < m, seperti yang f membagi n (f adalah faktor kecil n)?

Ini adalah masalah keputusan karena jawabannya ya atau tidak. Jika seseorang memberi kita contoh masalah (jadi mereka menyerahkan bilangan bulat kepada kami n dan m) dan bilangan bulat f dengan 1 < f < m, dan klaim itu f adalah faktor n (sertifikat), kita dapat memeriksa jawabannya waktu polinomial dengan melakukan pembagian n / f.


NP-Lengkap

NP-Complete adalah kelas kompleksitas yang mewakili himpunan semua masalah X di NP yang memungkinkan untuk mengurangi masalah NP lainnya Y untuk X dalam waktu polinomial.

Intuitif ini artinya kita bisa menyelesaikannya Y cepat jika kita tahu cara menyelesaikannya X segera. Tepat, Y direduksi menjadi X, jika ada algoritma waktu polinomial f untuk mengubah contoh y dari Y ke instance x = f(y) dari X dalam waktu polinomial, dengan properti yang jawabannya y adalah ya, jika dan hanya jika jawabannya f(y) ya.

Contoh 

3-SAT. Ini adalah masalah di mana kita diberi konjungsi (ANDs) dari 3-klausa disjunctions (OR), pernyataan bentuk

(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)

dimana masing-masing x_vij adalah variabel boolean atau negasi dari variabel dari daftar yang telah ditentukan sebelumnya (x_1, x_2, ... x_n).

Itu bisa ditunjukkan itu setiap masalah NP dapat dikurangi menjadi 3-SAT. Bukti ini bersifat teknis dan membutuhkan penggunaan definisi teknis NP (berdasarkan mesin Turing non-deterministik). Ini dikenal sebagai Teorema Cook.

Apa yang membuat masalah NP-lengkap penting adalah bahwa jika algoritma waktu polinomial deterministik dapat ditemukan untuk menyelesaikan salah satunya, setiap masalah NP dapat dipecahkan dalam waktu polinomial (satu masalah untuk mengatur semuanya).


NP-hard

Secara intuitif, ini adalah masalah yang ada setidaknya sekeras masalah NP-lengkap. Perhatikan bahwa masalah NP-hard tidak harus di NP, dan mereka tidak harus menjadi masalah keputusan.

Definisi yang tepat di sini adalah itu masalah X adalah NP-hard, jika ada masalah NP-complete Y, seperti yang Y direduksi menjadi X dalam waktu polinomial.

Tapi karena masalah NP-lengkap dapat dikurangi menjadi masalah NP-lengkap lainnya dalam waktu polinomial, semua masalah NP-lengkap dapat dikurangi menjadi masalah NP-hard di waktu polinomial. Kemudian, jika ada solusi untuk satu masalah NP-keras dalam waktu polinomial, ada solusi untuk semua masalah NP dalam waktu polinomial.

Contoh

Itu masalah terhenti adalah masalah NP-sulit. Ini adalah masalah yang diberikan program P dan masukan I, apakah akan berhenti? Ini adalah masalah keputusan tetapi tidak di NP. Jelas bahwa masalah NP-lengkap dapat direduksi menjadi yang satu ini. Sebagai contoh lain, masalah NP-lengkap adalah NP-hard.

Masalah NP-lengkap favorit saya adalah Masalah penyapu ranjau.


P = NP

Yang ini adalah masalah paling terkenal dalam ilmu komputer, dan salah satu pertanyaan terpenting yang paling penting dalam ilmu matematika. Bahkan, itu Clay Institute menawarkan satu juta dolar untuk solusi masalah (Stephen Cook's Langgan di situs web Clay cukup bagus).

Sudah jelas bahwa P adalah bagian dari NP. Pertanyaan terbuka adalah apakah masalah NP memiliki solusi waktu polinomial deterministik. Sebagian besar percaya bahwa mereka tidak melakukannya. Berikut adalah artikel terbaru tentang terbaru (dan pentingnya) masalah P = NP: Status masalah P versus NP.

Buku terbaik tentang masalah ini Komputer dan Daya Tarik oleh Garey dan Johnson.


1178
2017-12-07 01:46



Saya telah melihat-lihat dan melihat banyak penjelasan panjang. Berikut ini adalah bagan kecil yang mungkin berguna untuk diringkas:

Perhatikan bagaimana kesulitan meningkatkan dari atas ke bawah: apa saja NP dapat direduksi menjadi NP-Complete, dan apa saja NP-Complete dapat direduksi menjadi NP-Hard, semua dalam P (polinom) waktu.

Jika Anda dapat memecahkan masalah kelas yang lebih sulit dalam waktu P, itu berarti Anda menemukan cara menyelesaikan semua masalah yang lebih mudah dalam waktu P (misalnya, membuktikan P = NP, jika Anda mengetahui cara menyelesaikan masalah NP-Lengkap di P waktu).

____________________________________________________________
| Jenis Masalah | Dapat diverifikasi dalam waktu P | Dapat dipecahkan dalam waktu P | Meningkatkan Kesulitan
___________________________________________________________ | |
| P | Ya | Ya | |
| NP | Ya | Ya atau Tidak * | |
| NP-Lengkap | Ya | Tidak Diketahui | |
| NP-Hard | Ya atau Tidak ** | Unknown *** | |
____________________________________________________________ V

Catatan tentang Yes atau No entri:

  • * Masalah NP yang juga P dapat dipecahkan dalam waktu P.
  • ** Masalah NP-Hard yang juga NP-Complete dapat diverifikasi dalam waktu P.
  • *** Masalah NP-Complete (yang semuanya membentuk subset dari NP-hard) mungkin. Sisa NP keras tidak.

Saya juga menemukan diagram ini cukup berguna dalam melihat bagaimana semua jenis ini sesuai satu sama lain (lebih memperhatikan separuh bagian kiri diagram).


204
2017-10-22 06:08



Ini adalah jawaban yang sangat tidak resmi untuk pertanyaan yang diajukan.

Apakah 3233 dapat ditulis sebagai produk dari dua angka lain yang lebih besar dari 1? Apakah ada cara untuk berjalan di sekitar jalan Tujuh Jembatan Königsberg tanpa mengambil jembatan dua kali? Ini adalah contoh pertanyaan yang memiliki sifat yang sama. Mungkin tidak jelas bagaimana cara menentukan jawaban secara efisien, tetapi jika jawabannya 'ya', maka ada bukti singkat dan cepat untuk diperiksa. Dalam kasus pertama faktorisasi non-sepele dari 51; di kedua, rute untuk berjalan jembatan (pas kendala).

SEBUAH masalah keputusan adalah kumpulan pertanyaan dengan jawaban ya atau tidak yang hanya bervariasi dalam satu parameter. Katakanlah masalah COMPOSITE = {"Apakah n gabungan": n adalah integer} atau EULERPATH = {"Apakah grafik G memiliki jalur Euler? ": G adalah grafik terbatas}.

Sekarang, beberapa masalah keputusan mengarah pada algoritma yang efisien, jika tidak jelas. Euler menemukan algoritma yang efisien untuk masalah seperti "Seven Bridges of Königsberg" lebih dari 250 tahun yang lalu.

Di sisi lain, untuk banyak masalah keputusan, tidak jelas bagaimana mendapatkan jawabannya - tetapi jika Anda mengetahui beberapa informasi tambahan, sudah jelas bagaimana cara membuktikan Anda telah mendapatkan jawaban yang benar. KOMPOSIT seperti ini: Pembagian percobaan adalah algoritma yang jelas, dan itu lambat: untuk faktor nomor 10 digit, Anda harus mencoba sesuatu seperti 100.000 pembagi mungkin. Tetapi jika, misalnya, seseorang mengatakan kepada Anda bahwa 61 adalah pembagi dari 3233, pembagian panjang yang sederhana adalah cara yang efisien untuk melihat bahwa mereka benar.

Kelas kompleksitas NP adalah kelas masalah keputusan di mana jawaban 'ya' memiliki kekurangan untuk menyatakan, cepat untuk memeriksa bukti. Seperti KOMPOSIT. Satu hal penting adalah bahwa definisi ini tidak mengatakan apa pun tentang betapa sulitnya masalah itu. Jika Anda memiliki cara yang benar dan efisien untuk memecahkan masalah keputusan, tulis saja langkah-langkah dalam solusi adalah bukti yang cukup.

Riset algoritme berlanjut, dan algoritme pintar baru dibuat sepanjang waktu. Masalah yang mungkin Anda tidak tahu cara menyelesaikannya dengan efisien hari ini dapat berubah menjadi solusi yang efisien (jika tidak jelas) besok. Bahkan, butuh peneliti sampai 2002 untuk menemukan solusi yang efisien untuk COMPOSITE! Dengan semua kemajuan ini, orang benar-benar harus bertanya-tanya: Apakah ini tentang memiliki bukti singkat hanya ilusi? Mungkin setiap masalah keputusan yang cocok untuk bukti 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 dari berbagai NP yang terbukti sulit atau lebih keras daripada setiap masalah NP lainnya. Solusi efisien untuk masalah kepuasan boolean dapat digunakan untuk menciptakan solusi yang efisien ada yang lain masalah di NP. Segera setelah itu, Richard Karp menunjukkan bahwa sejumlah masalah keputusan lainnya dapat mencapai tujuan yang sama. Masalah-masalah ini, dalam arti masalah "yang paling sulit" di TN, menjadi dikenal sebagai NP-lengkap masalah.

Tentu saja, NP hanya kelas masalah keputusan. Banyak masalah tidak secara alami dinyatakan dengan cara ini: "temukan faktor-faktor N", "temukan jalur terpendek dalam grafik G yang mengunjungi setiap titik", "berikan satu set tugas variabel yang membuat ekspresi boolean berikut ini benar". Meskipun orang mungkin secara informal berbicara tentang beberapa masalah seperti "di NP", secara teknis itu tidak masuk akal - mereka bukan masalah keputusan. Beberapa masalah ini bahkan mungkin memiliki kekuatan yang sama seperti masalah NP-lengkap: solusi yang efisien untuk masalah-masalah (non-keputusan) akan mengarah langsung ke solusi efisien untuk masalah NP. Masalah seperti ini disebut NP-hard.


70
2017-12-07 02:42



Selain jawaban hebat lainnya, inilah jawabannya skema tipikal orang menggunakan untuk menunjukkan perbedaan antara NP, NP-Complete, dan NP-Hard:

enter image description here


49
2017-11-24 17:50



Cara termudah untuk menjelaskan P v. NP dan semacamnya tanpa membahas masalah teknis adalah dengan membandingkan "masalah kata" dengan "masalah pilihan ganda".

Ketika Anda mencoba memecahkan "masalah kata", Anda harus menemukan solusinya dari awal. Ketika Anda mencoba memecahkan "masalah pilihan ganda", Anda memiliki pilihan: memecahkannya sama seperti "masalah kata", atau mencoba memasukkan setiap jawaban yang diberikan kepada Anda, dan pilih jawaban kandidat yang sesuai.

Sering terjadi bahwa "masalah pilihan ganda" jauh lebih mudah daripada "masalah kata" yang sesuai: mengganti jawaban kandidat dan memeriksa apakah mereka cocok mungkin memerlukan usaha yang jauh lebih sedikit daripada menemukan jawaban yang benar dari awal.

Sekarang, jika kita akan menyetujui upaya yang mengambil 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 P v. 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 itu sulit?

Sekarang kita mengerti secara intuitif apa itu NP, kita harus menantang intuisi kita. Ternyata ada "masalah pilihan ganda" yang, dalam beberapa hal, yang paling sulit dari semuanya: jika seseorang akan menemukan solusi untuk salah satu masalah "yang paling sulit dari mereka semua" seseorang akan dapat menemukan solusi untuk SEMUA Masalah NP! Ketika Cook menemukan ini 40 tahun yang lalu, itu benar-benar mengejutkan. Masalah-masalah "yang paling sulit dari mereka semua" dikenal sebagai NP-hard. Jika Anda menemukan "solusi masalah kata" untuk salah satunya, Anda secara otomatis akan menemukan "solusi masalah kata" untuk setiap "masalah pilihan ganda yang mudah"!

Akhirnya, masalah NP-lengkap adalah masalah NP dan NP-hard secara bersamaan. Mengikuti analogi kami, mereka secara bersamaan "mudah karena masalah pilihan ganda" dan "yang paling sulit dari semuanya sebagai masalah kata".


40
2017-08-08 20:41



P (Waktu Polinomial): Seperti namanya sendiri, ini adalah masalah yang dapat diselesaikan dalam waktu polinomial.

NP (Non-deterministic-polynomial Time): 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. Kemudian, saya akan memberi Anda bukti yang dapat Anda verifikasi dengan mudah dalam waktu polinomial. 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 sekurang-kurangnya sama sulitnya dengan masalah yang paling sulit di NP. Jika kita dapat menyelesaikan masalah ini dalam waktu polinomial, kita dapat memecahkan masalah NP yang mungkin ada. Perhatikan bahwa masalah ini belum tentu masalah NP. Itu berarti, kami mungkin / tidak dapat memverifikasi solusi untuk masalah ini dalam waktu polinomial.

NP-Lengkap: 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.


34
2017-10-04 03:50



Saya pikir kita bisa menjawabnya dengan jauh lebih ringkas. Saya menjawab a pertanyaan terkait, dan menyalin jawaban saya dari sana

Tapi pertama-tama, masalah NP-hard adalah masalah yang kami tidak dapat membuktikan bahwa solusi waktu polinomial ada. NP-hardness dari beberapa "masalah-P" biasanya dibuktikan dengan mengubah masalah NP-hard yang sudah terbukti menjadi "masalah-P" dalam waktu polinomial.

Untuk menjawab pertanyaan lainnya, Anda harus terlebih dahulu memahami masalah NP-hard yang mana NP-complete. Jika masalah NP-hard termasuk dalam NP, maka NP-complete. Untuk menjadi anggota set NP, masalah perlu

(i) masalah keputusan,
  (ii) jumlah solusi untuk masalah harus terbatas dan setiap solusi harus memiliki panjang polinomial, dan
(iii) diberi solusi panjang polinomial, kita harus dapat mengatakan apakah jawaban untuk masalah adalah ya / tidak

Sekarang, mudah untuk melihat bahwa mungkin ada banyak masalah NP-hard yang tidak termasuk dalam set NP dan lebih sulit untuk dipecahkan. Sebagai contoh intuitif, versi pengoptimalan dari penjual keliling di mana kita perlu menemukan jadwal yang sebenarnya lebih sulit daripada versi keputusan penjual perjalanan di mana kita hanya perlu menentukan apakah jadwal dengan panjang <= k ada atau tidak.


16
2018-06-18 16:52



Masalah NP-complete adalah masalah yang sama-sama NP-Hard dan dalam NP kelas kompleksitas. Oleh karena itu, untuk menunjukkan bahwa setiap masalah yang diberikan adalah NP-complete, Anda perlu menunjukkan bahwa masalahnya adalah NP dan NP-hard.

Masalah yang ada dalam kompleksitas kelas NP dapat diselesaikan secara non-deterministik dalam waktu polinomial dan solusi yang mungkin (yaitu, sertifikat) untuk masalah di NP dapat diverifikasi untuk kebenaran dalam waktu polinomial.

Contoh solusi non-deterministik untuk masalah k-klik akan menjadi sesuatu seperti:

1) secara acak memilih simpul-simpul dari suatu grafik

2) verifikasi bahwa simpul-simpul ini membentuk sebuah klik.

Strategi di atas adalah polinomial dalam ukuran grafik input dan karena itu masalah k-clique berada di NP.

Perhatikan bahwa semua masalah yang dipecahkan secara deterministik dalam waktu polinomial juga dalam NP.

Menunjukkan bahwa masalah adalah NP-hard biasanya melibatkan pengurangan dari beberapa masalah NP-hard lainnya ke masalah Anda menggunakan pemetaan waktu polinomial: http://en.wikipedia.org/wiki/Reduction_(complexity)


15
2017-12-07 01:45



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 komputasional.

Bagi seseorang yang berpikir bahwa kompleksitas komputasinya hanya tentang P dan NP, di sini adalah sumber daya yang paling lengkap tentang masalah kompleksitas komputasional yang berbeda. 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 fundamental yang menggambarkan kelas.


5
2018-01-14 01:56