Kapan "X is NP-complete" menyiratkan "#X is # P-complete"?

Biarkan menunjukkan masalah (keputusan) dalam NP dan biarkan # menunjukkan versi penghitungannya. $X$ $X$

Dalam kondisi apa diketahui bahwa "X is NP-complete" "#X is # P-complete"? $\implies$

Tentu saja keberadaan reduksi pelit adalah satu kondisi seperti itu, tetapi ini jelas dan satu-satunya kondisi yang saya sadari. Tujuan utamanya adalah untuk menunjukkan bahwa tidak ada kondisi yang diperlukan.

Secara formal, seseorang harus mulai dengan masalah penghitungan # didefinisikan oleh fungsi dan kemudian mendefinisikan masalah keputusan pada string input sebagai ? $X$ $f : \{0,1\}^* \to \mathbb{N}$ $X$ $s$ $f(s) \ne 0$

cc.complexity-theory np-hardness counting-complexity Tyson Williams
sumber

Apakah Anda mencari sesuatu yang lebih dari "X adalah NP-lengkap di bawah pengurangan pelit"?

Joshua Grochow

@ usul: Tidak. Jika kita menghapus asumsi bahwa X adalah NP-lengkap, maka pencocokan bipartit adalah dalam P (jadi jelas bukan parsimoniously NP-complete dengan asumsi ) tetapi versi penghitungannya adalah # P-complete. Namun, jika kita benar-benar menginginkan X NP-selesai, maka dari atas kepala saya, saya tidak tahu masalah X sehingga: 1) X adalah NP-lengkap, 2) X tidak NP-lengkap di bawah pengurangan pelit, dan 3) #X adalah # P-complete. Tetapi saya belum benar-benar memikirkannya.

P \neq N P

$P \neq NP$

Joshua Grochow

Tetapi apakah ada masalah yang meniadakan hal ini? yaitu X adalah NP-complete dan #X tidak # P-complete?

Suresh Venkat

@YoshioOkamoto: itu membuktikan bahwa #X ∈ #P menyiratkan bahwa X ∈ NP . Itu ke arah yang salah dan merindukan masalah kelengkapan. Apa yang kita lihat pada dasarnya adalah apa persyaratan tambahan yang diperlukan agar keberadaan banyak-ke-satu pengurangan untuk masalah keputusan dalam NP (untuk masalah keputusan sewenang-wenang, atau dari masalah NP- lengkap) mensyaratkan adanya suatu pengurangan penghitungan yang efisien untuk masalah di # P (untuk masalah penghitungan sewenang-wenang, atau dari masalah #P -lengkap ).

Niel de Beaudrap

@ColinMcQuillan Bisa dinyatakan sebaliknya. Mulailah dengan masalah penghitungan dan tentukan masalah keputusan dari sana dan tanyakan apakah hasilnya nol.

Tyson Williams

Jawaban:

Makalah terbaru tentang pertanyaan ini tampaknya:

Noam Livne, Catatan tentang # P-kelengkapan hubungan menyaksikan-NP , Informasi Pemrosesan Surat, Volume 109, Edisi 5, 15 Februari 2009, Halaman 259-261 http://www.sciencedirect.com/science/article/pii/ S0020019008003141

yang memberikan beberapa kondisi yang cukup.

Menariknya, pengantar menyatakan "Sampai saat ini, semua set lengkap NP yang diketahui memiliki hubungan yang menentukan yang merupakan #P selesai", jadi jawaban untuk komentar Suresh adalah "tidak ada contoh yang diketahui".

Colin McQuillan
sumber

Fischer, Sophie, Lane Hemaspaandra, dan Leen Torenvliet. "Pengurangan saksi-isomorfik dan pencarian lokal." CATATAN PEREKAT DALAM MATEMATIKA MURNI DAN DITERAPKAN (1997): 207-224.

Pada awal bagian 3.5, mereka mengajukan pertanyaan berikut, "Secara khusus, apakah ada set lengkap NP yang berkaitan dengan beberapa skema saksi tidak #P-lengkap?"

Dan kemudian mereka membuktikan dalam Teorema 3.1 bahwa "Jika ada NP-set lengkap L yang berkaitan dengan beberapa hubungan menyaksikan R tidak # P-lengkap, maka ". $_L$ ${\bf P}$ $\not =$ ${\bf P^{\bf \#P}}$

Tayfun Pay
sumber