Menghitung jumlah penugasan yang memuaskan dalam CNF-SAT POSITIF

Kita tahu masalah menghitung jumlah penugasan yang memuaskan dalam formula boolean umum yang diberikan (CNF-SAT), formula DNF yang diberikan, atau bahkan formula 2SAT yang diberikan adalah masalah # P-complete .

Sekarang, pertimbangkan CNF-SAT tanpa literal negatif (tidak , selalu A ). Masalah keputusan sangat mudah (atur semua variabel ke TRUE dan periksa apakah tugasnya memenuhi rumus), tetapi bagaimana dengan menghitung jumlah tugas yang memuaskan? Apakah ini memiliki algoritma waktu polinomial? Atau ini masalah # P-complete.$\neg A$$A$

Ini masih # P-complete [1]. Masalah ini biasanya disebut sebagai montone (#) SAT. Monotone # 2-SAT sudah # P-complete (ini sama dengan menghitung simpul penutup grafik).

[1] Roth, Dan. "Pada kekerasan dari perkiraan alasan." Kecerdasan Buatan 82.1-2 (1996): 273-302.

Masalah ini adalah Monoton-SAT. Ini # P-Lengkap di bawah Cook Reductions. Ini adalah salah satu masalah yang "mudah untuk diputuskan tetapi sulit untuk dihitung." Saya merekomendasikan makalah berikut. Reducibilitas Diri dari Masalah Menghitung Keras dengan Versi Keputusan di P