Sebuah pertanyaan untuk # P-melengkapi bukti permanen dari Ben-Dor / Halevi

Dalam kertas Ben-Dor / Halevi [1] itu diberikan bukti lain bahwa permanen -Lengkap. Di bagian akhir makalah ini, mereka menunjukkan rantai reduksi IntPerm ∝ NoNegPerm ∝ 2PowerPerm ∝ 0/1-Perm sementara nilai permanen dipertahankan di sepanjang rantai. Karena jumlah tugas pemisah dari formula 3SAT Φ dapat diperoleh dari nilai permanen, itu cukup untuk menghitung permanen dari matriks 0 / 1- final. Sejauh ini baik.$\#P$

$$\begin{equation} \text{IntPerm} \propto \text{NoNegPerm} \propto \text{2PowersPerm} \propto \text{0/1-Perm} \end{equation}$$ $\Phi$$0/1$

Namun, hal ini juga diketahui bahwa permanen dari -matrix A sama dengan jumlah matchings sempurna di double cover bipartit G , yaitu, grafik dari matriks ( 0 A A t 0 ) . Dan angka ini dapat dihitung secara efisien jika G ternyata planar (menggunakan algoritma Kastelyens).$0/1$$\text{A}$$G$$\begin{pmatrix} 0 & \text{A} \\ \text{A}^t & 0 \end{pmatrix}$$G$

Jadi secara total ini berarti, seseorang dapat menghitung jumlah penugasan yang menyebalkan dari formula boolean jika grafik terakhir G adalah planar.$\Phi$$G$

Karena penanaman sangat tergantung pada rumus Φ , harapannya adalah, bahwa ada formula tertentu yang lebih sering mengarah ke penutup bipartit planar. Adakah yang tahu kalau pernah diselidiki seberapa besar kemungkinan G akan planar?$G$$\Phi$$G$

Karena menghitung solusi satiesfying adalah -complete, grafik akan pasti hampir selalu non-planar, tetapi saya tidak dapat menemukan petunjuk mengenai topik ini.$\#P$

[1] Amir Ben-Dor dan Shai Halevi. Zero-one permanen adalah # p-complete, bukti yang lebih sederhana. Dalam Simposium Israel ke-2 tentang Teori Sistem Komputasi, halaman 108-117, 1993. Natanya, Israel.

Topik ini telah diselidiki secara luas dalam beberapa tahun terakhir dengan nama Algoritma Holografik oleh para peneliti seperti Valiant, Cai, Lu, Xia, Lipton, dan lainnya. Pada dasarnya semua kasus traktat #CSP (menghitung masalah kepuasan kendala) telah diidentifikasi dalam hal teorema dikotomi (FP vs. # P-complete). Khususnya, perhitungan Matchgate telah diidentifikasi sebagai kelas spesifik dari masalah penghitungan yang menjadi dapat ditelusuri pada grafik planar . Lihat misalnya tautan ini untuk referensi lebih lanjut.

Biasanya masalah #CSP tidak tertimbang didefinisikan oleh serangkaian hubungan dan input ke masalah #CSP ( Γ ) adalah rumus Φ .$\Gamma$$\Gamma$$\Phi$

Jika hanya berisi relasi arity paling banyak 1, maka setiap input yang mungkin Φ sesuai dengan grafik dengan grafik bintang disjoint, yang planar. Terlebih lagi, jika Γ mengandung relasi arity 2 atau lebih, maka mudah untuk membuat instan yang bukan planar. (Pikirkan variabel sebagai simpul dari grafik dan batasan biner sebagai ujung antara variabel-variabel ini. Aritas yang lebih tinggi juga berfungsi. Dengan cara ini, setiap grafik dapat dibangun, paling tidak sebagai subgraf dari grafik lain.)$\Gamma$$\Phi$$\Gamma$

Dalam konstrast, Anda mengabaikan dan langsung bertanya tentang Φ mana yang mengarah ke grafik planar. Namun, setiap Φ mendefinisikan grafik (unik). Tidak ada ketidakpahaman seperti yang Anda sarankan dalam paragraf ini:$\Gamma$$\Phi$$\Phi$

Karena penanaman sangat tergantung pada rumus Φ , harapannya adalah, bahwa ada formula tertentu yang lebih sering mengarah ke penutup bipartit planar. Adakah yang tahu kalau pernah diselidiki seberapa besar kemungkinan G akan planar?$G$$\Phi$$G$