Мы знаем, что проблема подсчета количества удовлетворяющих назначений в данной общей булевой формуле (CNF-SAT), заданной формуле DNF или даже заданной формуле 2SAT является проблемой # P-полной .
Теперь рассмотрит CNF-SAT без отрицательного литерала (не , всегда A ). Решить задачу очень легко (установите все переменные в значение ИСТИНА и проверьте, удовлетворяет ли присвоение формуле), но как насчет подсчета количества удовлетворяющих назначений? Есть ли в нем алгоритм полиномиального времени? Или это # P-полная проблема.
источник