Apakah ada masalah NP-complete, sehingga versi keputusan dari masalah penghitungannya tidak PP-complete?

Setelah kami memperbaiki verifikasi deterministik waktu polinomial V (input, sertifikat), masalah NP yang sesuai adalah pertanyaan: Untuk input ini, apakah ada (ukuran polinomial) sertifikat yang ada sehingga V (input, sertifikat) mengembalikan Benar?

Masalah penghitungan yang terkait (kelas #P) adalah: Berapa banyak sertifikat yang ada sehingga V (input, sertifikat) mengembalikan Benar?

#P bukan kelas "masalah keputusan", tetapi kelas masalah penghitungan. Kelas "masalah keputusan" tradisional terdekat adalah PP, yang memiliki masalah dalam bentuk: Apakah mayoritas sertifikat menghasilkan V (input, sertifikat) mengembalikan Benar?

Saya tertarik pada versi keputusan dari masalah penghitungan yang terkait dengan masalah NP-complete + verifier tertentu, yang akan menjadi: Diberikan contoh input dan bilangan bulat positif K: Apakah ada setidaknya K sertifikat yang berbeda sehingga V (input, sertifikat) mengembalikan Benar?

Masalah keputusan ini jelas setara dengan versi penghitungan (melalui Pencarian Biner). Jika saya tidak salah, kelas semua "versi keputusan dari masalah penghitungan yang terkait dengan masalah NP" ini sama sulitnya dengan PP karena:

1) Masalah "penghitungan keputusan" ini dapat dibingkai ulang sebagai masalah mayoritas lainnya, dengan memilih definisi ad-hoc verifier di mana banyak sertifikat secara manual dianggap Benar atau Salah sehingga setidaknya ada sertifikat K Benar dalam yang asli jika dan hanya jika mayoritas Benar dalam masalah yang dihasilkan. Sama seperti contoh sederhana untuk mengilustrasikan gagasan pengurangan, jika ada di mana 8 sertifikat mungkin, dan kami ingin tahu apakah setidaknya ada 3 yang benar, kami dapat mengusulkan verifikasi yang berbeda yang memiliki 11 sertifikat yang mungkin: untuk 8 yang asli hanya memeriksa secara normal, dan untuk tiga lainnya ia segera mengembalikan True tanpa melihat input. Karena mayoritas 11 adalah 6, pemverifikasi baru ini menerima mayoritas sertifikat persis jika yang asli menerima setidaknya 3.

Dengan demikian, semua masalah ini ada di PP.

2) Versi "penghitungan keputusan" yang sesuai untuk setiap masalah PP-lengkap jelas akan menjadi PP-keras, karena menyelesaikan masalah mayoritas asli hanya dengan menyelesaikan masalah. Dengan demikian, masalah-masalah tersebut adalah PP-lengkap.$(input, \left \lfloor \frac{ totalCertificates}{2} \right \rfloor + 1)$

Jadi sekarang, pada akhirnya, dapatkah saya dengan jelas menyatakan pertanyaan saya, yang merupakan "versi yang lebih canggih" dari ide yang sama yang ditunjukkan dalam MAX, varian MAJ dari masalah lengkap NP :

Apakah ada masalah NP-complete sehingga versi keputusan dari masalah penghitungannya (yang ada di PP) bukan PP-complete?

Misalnya, dalam kasus Subset-Sum, masalah keputusan terkait yang saya minati adalah: Apakah setidaknya ada K himpunan bagian kosong dari jumlah nol?

Karena K gratis dan tidak terbatas mendekati setengah dari sertifikat, argumen dari jawaban lain tidak berlaku.

Menempatkan pertanyaan Anda dalam istilah yang lebih tepat, Anda bertanya apakah klaim berikut berlaku:

$* \hspace{1mm} R(x,y) \text{ is an NP-complete relation}\Rightarrow count_R \text{ is PP-complete}$

Di mana didefinisikan sebagai berikut:$count_R$

$count_R=\left\{(x,k) \big| \hspace{1mm} \left\lvert\left\{y : R(x,y)\right\}\right\rvert\ge k\right\}$ .

Kami menyebut relasi NP-lengkap jika dapat dihitung dalam waktu polinomial, dan bahasa yang didefinisikannya adalah NP-complete.$R(x,y)$$L_R=\left\{x | \exists y \hspace{1mm} R(x,y)=1\right\}$

Kami berbicara dalam hal hubungan, karena seperti yang Anda sebutkan, versi penghitungan harus didefinisikan relatif terhadap beberapa verifikasi tertentu.

Tampaknya ini adalah pertanyaan terbuka, seperti (*) menyiratkan:

$** \hspace{1mm} R(x,y) \text{ is an NP-complete relation}\Rightarrow \#R\text{ is #P-complete}$

Di mana .$\#R(x)=\left\lvert \left\{y : R(x,y)\right\} \right\rvert$

Untuk melihat mengapa * mengimplikasikan hal di atas, misalkan berupa hubungan NP-complete. Menggunakan (*), adalah PP selesai, jadi . Dalam hal ini, dan karenanya adalah -lengkap (gunakan pencarian biner, di mana dalam setiap cutoff Anda menerapkan pengurangan dari untuk dan kueri oracle pada hasilnya).$R(x,y)$$count_R$$count_{\text{SAT}}\le_p count_R$$\#SAT\in\mathsf{FP}^{\# R}$$\#R$$\# P$$count_{\text{SAT}}$$count_R$$\#R$

Setahu saya, (**) saat ini terbuka. Lihat pertanyaan terkait ini dari cstheory. Juga terkait .