Menghitung pengurangan dari #SAT ke #HornSAT?

Apakah mungkin untuk menemukan pengurangan penghitungan dari #SAT ke #HornSAT? Saya belum menemukan pertanyaan ini diposting di sini, jadi memutuskan untuk memeriksa apakah ada yang punya jawaban untuk ini. Biarkan saya menjelaskan apa yang saya maksud dengan menghitung pengurangan.

Misalkan adalah dua masalah penghitungan. Sebagai contoh, #SAT menanyakan berapa banyak tugas yang memuaskan yang ada untuk contoh spesifik , dan adalah masalah penghitungan yang sama dalam menemukan jumlah saksi. Sebuah pengurangan penghitungan lemah pelit dari ke terdiri dari sepasang waktu polinomial fungsi dihitung dan sedemikian rupa sehingga . Dalam hal bahwa , ini dikenal sebagai reduksi penghitungan yang sangat pelit. ϕ f , g f g σ : { 0 , 1 } ∗ → { 0 , 1 } ∗ τ : { 0 , 1 } ∗ × N → N f ( x ) = τ ( x , g ( σ ( x ) $f,g : \{0,1\}^* \to \mathbb N$$\phi$$f,g$$f$$g$$\sigma : \{0,1\}^* \to \{0,1\}^*$$\tau : \{0,1\}^* \times \mathbb N \to \mathbb N$$f(x) = \tau (x, g(\sigma(x)))$$f(x) = g(\sigma(x))$

Saya dapat melihat bahwa jika ada pengurangan penghitungan seperti dari #SAT ke #HornSAT, itu haruslah pengurangan yang sangat pelit: pengurangan yang kuat akan menyiratkan bahwa instance #SAT dan #HornSAT akan memiliki jumlah solusi nol atau tidak nol sama sekali, dan dengan asumsi bahwa , ini tidak mungkin (seperti HornSAT ∈ P sedangkan SAT adalah N P -complete).$\mathsf P \ne \mathsf{NP}$$\in \mathsf P$$\mathsf{NP}$

Jadi pertanyaan saya adalah: apakah ada pengurangan penghitungan pelit lemah dari #SAT ke #HornSAT? Jika demikian, adakah yang bisa tolong beri saya referensi?

Posting ini membahas # P-kelengkapan # Monotone-2SAT di bawah reduksi pelit lemah. Jika Anda meniadakan semua literal dalam formula monoton 2-CNF , Anda mendapatkan formula Horn 2-CNF ψ dengan jumlah tugas yang memuaskan yang sama.$\phi$$\psi$