Baca "Pengurangan Di Antara Masalah Kombinatorial" oleh Karp.
Paul Hankin
Jawaban:
146
Untuk menunjukkan bahwa masalah NP selesai, Anda perlu:
Tunjukkan di NP
Dengan kata lain, diberikan beberapa informasi C, Anda dapat membuat algoritma waktu polinomial Vyang akan memverifikasi untuk setiap masukan yang mungkin Xapakah Xada di domain Anda atau tidak.
Contoh
Buktikan bahwa masalah penutup simpul (yaitu, untuk beberapa graf G, apakah ia memiliki satu set ukuran penutup simpul ksedemikian rupa sehingga setiap tepi di Gmemiliki setidaknya satu simpul dalam set penutup ?) Ada di NP:
masukan kami Xadalah beberapa grafik Gdan beberapa angka k(ini dari definisi masalah)
Jadikan informasi kami Csebagai "setiap subset yang mungkin dari simpul dalam Gukuran grafik k"
Kemudian kita dapat menulis algoritma Vyang, diberikan G, kdan C, akan mengembalikan apakah kumpulan simpul itu adalah penutup simpul Gatau tidak, dalam waktu polinomial .
Kemudian untuk setiap graf G, jika ada beberapa "kemungkinan subset dari simpul dalam Gukuran k" yang merupakan penutup simpul, maka Gmasuk NP.
Perhatikan bahwa kita tidak perlu mencari Cdalam waktu polinomial. Jika kita bisa, masalahnya ada di `P.
Perhatikan bahwa algoritme Vharus berfungsi untuk setiapG , untuk beberapa C. Untuk setiap masukan harus ada informasi yang dapat membantu kami memverifikasi apakah masukan tersebut ada di domain bermasalah atau tidak. Artinya, tidak boleh ada masukan yang informasinya tidak ada.
Buktikan itu NP Hard
Ini melibatkan mendapatkan masalah NP-complete yang diketahui seperti SAT , kumpulan ekspresi boolean dalam bentuk:
(A atau B atau C) dan (D atau E atau F) dan ...
di mana ekspresi itu memuaskan , apakah ada beberapa pengaturan untuk boolean ini, yang membuat ekspresi itu benar .
Kemudian kurangi masalah NP-complete menjadi masalah Anda dalam waktu polinomial .
Artinya, dengan beberapa masukan Xuntuk SAT(atau masalah NP-complete apa pun yang Anda gunakan), buat beberapa masukan Yuntuk masalah Anda, seperti Xdalam SAT jika dan hanya jika Yada dalam masalah Anda. Fungsi tersebut f : X -> Yharus berjalan dalam waktu polinomial .
Dalam contoh di atas, inputnya Yadalah grafik Gdan ukuran tutup puncak k.
Untuk bukti lengkap , Anda harus membuktikan keduanya:
yang Xada di SAT=> Ydalam masalah Anda
dan Ydalam masalah Anda => Xdalam SAT.
Jawaban marcog memiliki kaitan dengan beberapa masalah NP-complete lainnya yang dapat Anda kurangi menjadi masalah Anda.
Catatan kaki: Pada langkah 2 ( Buktikan bahwa ini NP-hard ), mengurangi masalah NP-hard (belum tentu NP-complete) ke masalah saat ini akan dilakukan, karena masalah NP-complete adalah bagian dari masalah NP-hard (yaitu juga di NP).
Saya ingin tahu apakah ada data yang hilang atau alasan melingkar di balik ini. Maksud saya bagaimana cara 'membuktikan' suatu masalah ada di NP tanpa merujuk ke masalah lain yang 'sudah ada di NP'? Ini seperti mengatakan "terbuat dari besi karena bagiannya dikenal besi", itu bukan bukti besi.
Hernán Eche
6
Sejauh yang saya ingat, ada teorema yang disebut Teorema Cook-Levin yang menyatakan bahwa SAT adalah NP-complete. Bukti itu sedikit lebih rumit daripada yang saya uraikan di atas dan saya rasa saya tidak bisa menjelaskannya dengan kata-kata saya sendiri.
Laila Agaev
4
Lebih tepatnya, Teorema Cook-Levin menyatakan bahwa SAT adalah NP-complete: masalah apa pun di NP dapat dikurangi dalam waktu polinomial oleh mesin Turing deterministik ke masalah menentukan apakah rumus Boolean memuaskan (SAT). Jadi itu bagian yang hilang yang Anda tanyakan. Jika Anda mencari teorema di Wikipedia, ada bukti, dan Anda dapat merujuk teorema tersebut dalam bukti Anda. Meskipun demikian, mengurangi SAT menjadi masalah tertentu adalah cara saya diajar untuk membuktikan kelengkapan NP.
Laila Agaev
Jadi pertanyaan saya akhirnya adalah jika SAT dapat diselesaikan dalam polinomial yaitu masalah P = NP .. Terima kasih atas jawaban Anda.
Hernán Eche
Bisakah Anda menjelaskan mengapa kami tidak dapat mengurangi masalah NP-hard menjadi masalah yang kami inginkan, pada langkah kedua? Apakah itu harus menjadi masalah NP-complete?
MLT
23
Anda perlu mengurangi masalah NP-Complete menjadi masalah yang Anda miliki. Jika reduksi bisa dilakukan dalam waktu polinomial maka Anda sudah membuktikan bahwa soal Anda NP-complete, jika soal sudah ada di NP, karena:
Ini tidak lebih mudah daripada masalah NP-complete, karena dapat direduksi menjadi masalah dalam waktu polinomial yang membuat masalah menjadi NP-Hard.
Beri +1 seseorang yang menjelaskan dengan mudah. alih-alih mengatakan banyak referensi ke kata kunci yang hampir tidak saya mengerti.
ColacX
22
Kalimat pertama adalah back-to-front: Anda perlu mengurangi masalah NP-complete yang diketahui menjadi masalah Anda sendiri. Ini menunjukkan bahwa masalah Anda setidaknya sekeras masalah NP-complete yang diketahui. Bagian (b) juga salah: jika Anda sudah menemukan pengurangannya maka Anda sudah tahu bahwa masalah Anda adalah NP-hard; satu-satunya pertanyaan adalah apakah itu ada di NP sama sekali (beberapa masalah, seperti Masalah Halting, tidak). Jika NP-hard dan NP, maka NP-complete (yaitu "NP-complete" lebih spesifik daripada "NP-hard").
j_random_hacker
1
Saya tidak akan mengatakan a) mengarah pada kontradiksi, karena kita tidak tahu bahwa P! = NP.
Chiel ten Brinke
8
Untuk membuktikan bahwa masalah L adalah NP-complete, kita perlu melakukan langkah-langkah berikut:
Buktikan masalah Anda L milik NP (yaitu dengan memberikan solusi, Anda dapat memverifikasinya dalam waktu polinomial)
Pilih masalah NP-complete yang diketahui L '
Jelaskan algoritma f yang mengubah L 'menjadi L
Buktikan bahwa algoritme Anda benar (secara formal: x ∈ L 'jika dan hanya jika f (x) ∈ L)
Buktikan bahwa algo f berjalan dalam waktu polinomial
Pertama, Anda menunjukkan bahwa itu terletak di NP.
Kemudian Anda menemukan masalah lain yang sudah Anda ketahui adalah NP lengkap dan menunjukkan bagaimana Anda mengurangi masalah NP Hard secara polinomial ke masalah Anda.
Tidak. Anda harus menunjukkan bahwa Anda dapat mengurangi dari masalah NP lengkap menjadi masalah NP Anda untuk membuktikan kelengkapan NP DAN membuktikannya sama sekali. NP hard tidak ikut campur, kecuali Anda tidak dapat membuktikannya di NP.
mrmemio29
6
Pahami bagian dari masalah NP Complete
Buktikan NP Hardness: Kurangi instance arbitrary dari masalah NP lengkap menjadi instance masalah Anda. Ini adalah bagian terbesar dari kue dan di mana keakraban dengan masalah NP Complete terbayar. Pengurangan akan lebih atau kurang sulit tergantung pada masalah NP Selesai yang Anda pilih.
Buktikan bahwa masalah Anda ada di NP: rancang algoritme yang dapat memverifikasi dalam waktu polinomial apakah sebuah instance adalah solusi.
Jawaban:
Untuk menunjukkan bahwa masalah NP selesai, Anda perlu:
Tunjukkan di NP
Dengan kata lain, diberikan beberapa informasi
C, Anda dapat membuat algoritma waktu polinomialVyang akan memverifikasi untuk setiap masukan yang mungkinXapakahXada di domain Anda atau tidak.Contoh
Buktikan bahwa masalah penutup simpul (yaitu, untuk beberapa graf
G, apakah ia memiliki satu set ukuran penutup simpulksedemikian rupa sehingga setiap tepi diGmemiliki setidaknya satu simpul dalam set penutup ?) Ada di NP:masukan kami
Xadalah beberapa grafikGdan beberapa angkak(ini dari definisi masalah)Jadikan informasi kami
Csebagai "setiap subset yang mungkin dari simpul dalamGukuran grafikk"Kemudian kita dapat menulis algoritma
Vyang, diberikanG,kdanC, akan mengembalikan apakah kumpulan simpul itu adalah penutup simpulGatau tidak, dalam waktu polinomial .Kemudian untuk setiap graf
G, jika ada beberapa "kemungkinan subset dari simpul dalamGukurank" yang merupakan penutup simpul, makaGmasukNP.Perhatikan bahwa kita tidak perlu mencari
Cdalam waktu polinomial. Jika kita bisa, masalahnya ada di `P.Perhatikan bahwa algoritme
Vharus berfungsi untuk setiapG, untuk beberapaC. Untuk setiap masukan harus ada informasi yang dapat membantu kami memverifikasi apakah masukan tersebut ada di domain bermasalah atau tidak. Artinya, tidak boleh ada masukan yang informasinya tidak ada.Buktikan itu NP Hard
Ini melibatkan mendapatkan masalah NP-complete yang diketahui seperti SAT , kumpulan ekspresi boolean dalam bentuk:
di mana ekspresi itu memuaskan , apakah ada beberapa pengaturan untuk boolean ini, yang membuat ekspresi itu benar .
Kemudian kurangi masalah NP-complete menjadi masalah Anda dalam waktu polinomial .
Artinya, dengan beberapa masukan
XuntukSAT(atau masalah NP-complete apa pun yang Anda gunakan), buat beberapa masukanYuntuk masalah Anda, sepertiXdalam SAT jika dan hanya jikaYada dalam masalah Anda. Fungsi tersebutf : X -> Yharus berjalan dalam waktu polinomial .Dalam contoh di atas, inputnya
Yadalah grafikGdan ukuran tutup puncakk.Untuk bukti lengkap , Anda harus membuktikan keduanya:
yang
Xada diSAT=>Ydalam masalah Andadan
Ydalam masalah Anda =>XdalamSAT.Jawaban marcog memiliki kaitan dengan beberapa masalah NP-complete lainnya yang dapat Anda kurangi menjadi masalah Anda.
Catatan kaki: Pada langkah 2 ( Buktikan bahwa ini NP-hard ), mengurangi masalah NP-hard (belum tentu NP-complete) ke masalah saat ini akan dilakukan, karena masalah NP-complete adalah bagian dari masalah NP-hard (yaitu juga di NP).
sumber
Anda perlu mengurangi masalah NP-Complete menjadi masalah yang Anda miliki. Jika reduksi bisa dilakukan dalam waktu polinomial maka Anda sudah membuktikan bahwa soal Anda NP-complete, jika soal sudah ada di NP, karena:
Ini tidak lebih mudah daripada masalah NP-complete, karena dapat direduksi menjadi masalah dalam waktu polinomial yang membuat masalah menjadi NP-Hard.
Lihat akhir dari http://www.ics.uci.edu/~eppstein/161/960312.html untuk lebih lanjut.
sumber
Untuk membuktikan bahwa masalah L adalah NP-complete, kita perlu melakukan langkah-langkah berikut:
sumber
Pertama, Anda menunjukkan bahwa itu terletak di NP.
Kemudian Anda menemukan masalah lain yang sudah Anda ketahui adalah NP lengkap dan menunjukkan bagaimana Anda mengurangi masalah NP Hard secara polinomial ke masalah Anda.
sumber
sumber