Status PP-kelengkapan MAJ3SAT

PERTANYAAN SINGKAT: Apakah MAJ-3CNF masalah PP-lengkap di bawah banyak-satu pengurangan?

VERSI LAMA: Sudah diketahui bahwa MAJSAT (memutuskan apakah mayoritas penugasan hukuman proporsional memenuhi hukuman) adalah PP-lengkap di bawah banyak-satu pengurangan dan #SAT adalah # P-lengkap di bawah pengurangan pelit. Juga jelas bahwa # 3CNF (yaitu, #SAT terbatas pada formula 3-CNF) adalah # P-complete, karena pengurangan Cook-Levin adalah pelit dan menghasilkan 3-CNF (pengurangan ini sebenarnya digunakan dalam buku Papadimitriou untuk tampilkan # P-kelengkapan #SAT).

Tampaknya argumen serupa harus membuktikan bahwa MAJ-3CNF adalah PP-lengkap di bawah banyak pengurangan (MAJ-kCNF adalah MAJSAT terbatas pada formula kCNF; yaitu setiap klausa memiliki k literal).

Namun, dalam presentasi oleh Bailey, Dalmau dan Kolaitis, "Transisi Fase Masalah Kepuasan Lengkap PP", penulis menyebutkan bahwa "MAJ3SAT tidak dikenal sebagai PP Lengkap" (presentasi di https: //users.soe.ucsc .edu / ~ kolaitis / pembicaraan / ppphase4.ppt ). Kalimat ini sepertinya tidak muncul di makalah terkait mereka, hanya dalam presentasi mereka.

Pertanyaan: Dapatkah bukti bahwa # 3CNF adalah # P-complete memang diadaptasi untuk membuktikan bahwa MAJ3CNF adalah PP-complete? Mengingat pernyataan oleh Bailey et al., Tampaknya tidak; jika buktinya tidak dibawa, maka: Apakah ada bukti bahwa MAJ-3CNF adalah PP-lengkap? Jika tidak, apakah ada intuisi tentang perbedaan antara PP dan #P sehubungan dengan hasil ini?

$\mathsf{MAJ3CNF}$$\mathsf{PP}$

$\mathsf{PP}$

$\mathsf{MAJORITY \ SAT}$$\mathsf{PP}$$k \geq 3$$\mathsf{MAJORITY}$ $\mathsf{kSAT}$$\mathsf{PP}$

[ http://www.sciencedirect.com/science/article/pii/S0166218X06004665 ]

$\mathsf{\#CNF}$$\mathsf{\#P}$$\mathsf{\#3CNF}$$\mathsf{\#P}$

$\phi = (x_1 \vee x_2 \vee x_3 \vee x_4)$

yang diubah menjadi

$\phi'=(x_1 \vee x_2 \vee y) \wedge (y \leftrightarrow (x_3 \vee x_4))$

$y$

$\psi= (x_1 \vee x_2 \vee y) \wedge (\neg y \vee x_3 \vee x_4) \wedge (y \vee \neg x_3 ) \wedge (y \vee \neg x_4).$

$\phi$$\psi$

$\mathsf{\#P}$$\mathsf{MAJ3CNF}$$\mathsf{PP}$$\mathsf{MAJ3CNF}$$\mathsf{PP}$

$\mathsf{MAJ3CNF}$$\mathsf{\#P}$$\mathsf{PP}$$\mathsf{\#3CNF}$$\mathsf{D\#3CNF}$$\phi$$m \geq 0$$\phi$$m$$\mathsf{D\#3CNF}$$\mathsf{D\#3CNF}$$\mathsf{PP}$$\mathsf{MAJ3CNF}$$\mathsf{D\#3CNF}$