# P-selesaikan masalah yang versi keputusannya ada di P

14

1) Apakah mungkin untuk memiliki pengurangan parsimoni dari masalah # P-complete #A ke masalah penghitungan #B ketika (versi keputusan) A adalah NP-complete dan B berada di P?

Misalnya, dapatkah ada pengurangan pelit dari #SAT ke #B, ketika B ada di P?

2) Jika B ada di P, apa saja kemungkinan berbeda untuk kompleksitas #B?

cc.complexity-theory complexity-classes counting-complexity marjoonjan
sumber

Jawaban:

20

Jika Anda bersikeras untuk mengurangi pelit (di mana jumlah solusi dipertahankan) Anda tidak dapat memiliki pengurangan seperti itu kecuali P = NP karena algoritma keputusan untuk non-kekosongan solusi untuk B akan memberi Anda algoritma keputusan untuk non-kekosongan solusi untuk A. Di sisi lain, jika Anda mengizinkan pengurangan jenis lain, Anda dapat memiliki kasing semacam itu. Sebagai contoh, Valiant menunjukkan bahwa #SAT mengurangi masalah penghitungan kecocokan sempurna dalam grafik bipartit: pengurangan dimulai dengan rumus- CNF dan membangun grafik bipartit G yang jumlah kecocokan sempurna mod 2 8 m + 1 adalah 4 m dikalikan jumlah penugasan F yang memuaskan , di manaFG28m+14mF adalah jumlah kejadian literal di F . Perhatikan bagaimana ini bukan pengurangan pelit, tapi pengurangan tetap karena Anda dapat memulihkan jumlah memuaskan tugas dari F dari jumlah matchings sempurna G .mFFG

Lihat Bab 18 dalam buku "Kompleksitas Komputasi" Papadimitriou untuk penjelasan yang jelas tentang ini.

Slimton
sumber
7

Jawaban untuk pertanyaan 2 adalah bahwa kompleksitas masalah penghitungan #B pada dasarnya bisa apa saja (bahkan tidak bisa dihitung). Lebih tepatnya, pembatasan bahwa versi keputusan dalam P tidak memiliki implikasi pada kompleksitas versi penghitungan. Ini karena Anda dapat menambahkan solusi dummy ke masalah hubungan apa pun sehingga versi keputusan menjadi sepele (jawabannya menjadi selalu ya) tanpa mengubah kompleksitas versi penghitungan.

Tsuyoshi Ito
sumber
1
kenapa kamu bilang begitu? "(bahkan tidak bisa dihitung)" Jelas bahwa jika B adalah masalah keputusan dalam P maka #B ada di #P, langsung dari definisi kelas #P! tetapi membuktikan #B juga # P-com adalah penting, dan menambahkan solusi dummy tidak akan berpengaruh pada kompleksitas penghitungan. Anda setuju?
marjoonjan
@marjoonjan: “Jelas bahwa jika B adalah masalah keputusan dalam P maka #B di #P, langsung dari definisi kelas #P” Itu salah. Juga, saya mendapat kesan bahwa Anda percaya bahwa masalah keputusan B secara unik menentukan masalah penghitungan #B, tetapi tidak demikian halnya, seperti yang saya jelaskan dalam jawaban ini.
Tsuyoshi Ito