Semua masalah NP berkurang menjadi masalah NP-complete: jadi bagaimana bisa masalah NP tidak menjadi NP-complete?

10

Buku saya menyatakan ini

  • Jika masalah keputusan B dalam P dan A dikurangi menjadi B, maka masalah keputusan A ada di P.
  • Masalah keputusan B adalah NP-lengkap jika B di NP dan untuk setiap masalah di A di NP, A dikurangi menjadi B.
  • Masalah keputusan C adalah NP-lengkap jika C di NP dan untuk beberapa NP-menyelesaikan masalah B, B berkurang menjadi C.

Jadi pertanyaan saya adalah

  1. Jika B atau C dalam NP-complete, dan semua masalah di NP mereduksi menjadi NP-complete problem, menggunakan aturan pertama, bagaimana setiap masalah NP tidak bisa NP selesai?
  2. Jika A dikurangi menjadi B, apakah B mengurangi menjadi A?
complexity-theory np-complete decision-problem rubixibuc
sumber
2
Fakta menarik terkait dengan nomor 1 Anda: Jika P tidak sama dengan NP, kami tahu bahwa pasti ada masalah NP yang tidak lengkap NP (ini disebut teorema Ladner. Lihat NP Intermediate ). Yang aneh adalah bahwa kami tidak yakin akan masalah perhitungan umum yang sesuai dengan kategori ini. Masalah yang digunakan dalam teorema Ladner secara artifisial dibangun untuk membuktikan teorema tersebut, tetapi secara praktis tidak penting.
Lucas Cook
4
@Lucas, Anjak piutang dan GraphIso juga diperkirakan sebagai NPI, juga lihat ini .
Kaveh
@Kaveh: Daftar kandidat NPI yang bagus, terima kasih! Untuk memperjelas, saya mengatakan bahwa kami tidak "yakin" tentang masalah NPI alami dengan kepastian yang sama dengan masalah Ladner. Yaitu, jika , satu-satunya masalah NPI yang diketahui pasti adalah masalah buatan yang terkait dengan hierarki Ladner. P≠NP
Lucas Cook

Jawaban:

13

Jika A dikurangi menjadi B, apakah B mengurangi menjadi A?

Tidak. Untuk contoh yang benar-benar dibuat-buat, setiap kemungkinan masalah yang dapat dihitung A dapat direduksi ke Masalah Pemutusan: cukup masukkan sebagai input algoritme yang menyelesaikan masalah A tetapi dengan while(true)ditempel di bagian akhir setelah kasus benar atau salah. Namun, kita tahu bahwa masalah Berhenti tidak dapat dihitung sehingga tidak dapat direduksi menjadi algoritma A.

Ide dasarnya adalah bahwa jika ada pengurangan dari A ke B Anda dapat belajar bahwa B setidaknya sama sulitnya untuk dipecahkan maka A dan membutuhkan algoritma yang setidaknya sama kuatnya.

Jadi jika masalah A direduksi menjadi masalah B yang mudah, maka kita dapat menyimpulkan bahwa A mudah (karena reduksi memberi kita algoritma yang efisien) dan jika masalah yang sulit A dikurangi menjadi masalah B, kita dapat menyimpulkan bahwa B juga sulit ( karena jika B mudah maka A harus mudah juga). Namun masih ada kemungkinan melakukan pengurangan konyol dari masalah mudah menjadi masalah sulit, tetapi dalam kasus ini kita tidak dapat menyimpulkan kesimpulan.

hugomg
sumber
8

Jika B atau C di NP Lengkap, dan semua masalah di NP dikurangi menjadi NP Lengkap, menggunakan aturan pertama, bagaimana mungkin masalah NP tidak lengkap NP?

Aturan pertama adalah tentang masalah dalam P. Ini tidak ada hubungannya dengan kelengkapan NP. Jika masalah A adalah NP Lengkap dan masalah B berkurang menjadi A, itu tidak berarti bahwa B adalah NP Lengkap.

Jika A mengurangi menjadi B apakah B mengurangi ke A?

Tidak secara umum, tidak.

sepp2k
sumber
"Tidak secara umum, tidak.", Mengapa? Sedikit penjelasan mungkin juga berguna untuk pemula. Juga penjelasan untuk jawaban pertama Anda harus diberikan.
nbro
-1

Saya hanya punya ide dasar tentang Masalah NPC dan NP. Tetapi Yang ingin saya komentari adalah tentang "Jika A dikurangi menjadi B maka B dikurangi menjadi A?"

Cukup pertimbangkan himpunan A yang memiliki elemen {2,3,4,5} dan set B yang memiliki {3,4}. Jadi A dapat direduksi menjadi B. Namun B tidak dapat direduksi menjadi A. Sebaliknya B dapat diperluas ke A jika B mendapatkan elemen {2,5}.

Tetapi jika A dan B memiliki hal yang sama. maka A dapat direduksi menjadi B atau B dapat direduksi menjadi A.

Naveen CS
sumber
Ini sama sekali bukan ide pengurangan yang tepat. Pengurangan bukan tentang set elemen yang mendapatkan atau kehilangan. Alih-alih, ini tentang kemampuan untuk mengubah instance dari satu masalah menjadi masalah lain menggunakan mesin / algoritma Turing.
jmite
Baik. Jadi, jika ada masalah yang direduksi menjadi yang lain menggunakan algoritma apa pun maka tidak mungkin untuk mendapatkan kembali masalah dari pengurangan output menggunakan algoritma yang sama lagi.
Naveen CS
1
Saya tidak sepenuhnya yakin apa yang Anda maksud, tetapi saya pikir itu tidak mungkin. Jika saya tidak salah, pengurangan ini bisa banyak ke satu. A dikurangi menjadi B jika sejumlah panggilan polinom ke penyelesaian subrutin B memungkinkan A untuk diselesaikan dalam waktu polinomial. Contoh berbeda dari A dapat memanggil panggilan dengan contoh yang sama dari B.
jmite
2
Pertanyaannya adalah tentang masalah keputusan, bukan tentang set. Bagaimana berguna untuk melihat set? Menggunakan kata "dikurangi" berarti bahwa satu set adalah superset dari yang lain bahkan bukan terminologi yang umum.
Gilles 'SANGAT berhenti menjadi jahat'