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.
fuente