Подсчет количества удовлетворяющих заданий в ПОЗИТИВНОМ CNF-SAT

13

Мы знаем, что проблема подсчета количества удовлетворяющих назначений в данной общей булевой формуле (CNF-SAT), заданной формуле DNF или даже заданной формуле 2SAT является проблемой # P-полной .

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

Mohemnist
источник

Ответы:

20

Это еще # P-complete [1]. Эта проблема обычно называется montone (#) SAT. Монотонное # 2-SAT уже # P-завершено (это эквивалентно подсчету покрытий вершин графа).

[1] Рот, Дан. «О твердости приближенных рассуждений». Искусственный интеллект 82.1-2 (1996): 273-302.

holf
источник