Contando o número de tarefas satisfatórias em um CNF-SAT POSITIVO

13

Sabemos que o problema de contar o número de atribuições satisfatórias em uma determinada fórmula booleana geral (CNF-SAT), em uma fórmula DNF ou em uma fórmula 2SAT é um problema # P-complete .

Agora, considere um CNF-SAT sem literal negativo (sem negativo , sempre ). O problema de decisão é muito fácil (defina todas as variáveis ​​como VERDADEIRO e verifique se a tarefa está satisfazendo a fórmula), mas e quanto a contar o número de tarefas satisfatórias? Isso tem um algoritmo de tempo polinomial? Ou é um problema # P-completo.¬UMAUMA

Mohemnist
fonte

Respostas:

20

Ainda está # P-completo [1]. Esse problema geralmente é chamado de montone (#) SAT. O monótono # 2-SAT já está # P-complete (isso é equivalente à contagem de capas de vértices de um gráfico).

[1] Roth, Dan. "Sobre a dureza do raciocínio aproximado." Artificial Intelligence 82.1-2 (1996): 273-302.

holf
fonte