Contando el número de tareas satisfactorias en un CNF-SAT POSITIVO

13

Conocemos el problema de contar el número de asignaciones satisfactorias en una fórmula booleana general dada (CNF-SAT), una fórmula DNF dada, o incluso una fórmula 2SAT dada es un problema # P-completo .

Ahora, considere un CNF-SAT sin literal negativo (no , siempre A ). El problema de decisión es muy fácil (establezca todas las variables en VERDADERO y verifique si la asignación cumple con la fórmula), pero ¿qué pasa con el número de asignaciones satisfactorias? ¿Tiene esto un algoritmo de tiempo polinómico? O es un problema # P-completo.¬UNUN

Mohemnista
fuente

Respuestas:

20

Esto todavía es # P-completo [1]. Este problema generalmente se conoce como montone (#) SAT. Monotono # 2-SAT ya está # P-completo (esto es equivalente a contar las cubiertas de vértices de un gráfico).

[1] Roth, Dan. "Sobre la dureza del razonamiento aproximado". Inteligencia Artificial 82.1-2 (1996): 273-302.

holf
fuente