Un algoritmo para calcular #2SAT

Abstract

Resumen. El problema de conteo de modelos en frmulas booleanas pertenece a la clase #P-completo. Por tal motivo, no existe algoritmo qu, de forma eficiente, calcule el nmero exacto de modelos de una frmula booleana. En este artculo, se presenta una implementacin para contar el nmero de modelos de una frmula booleana basada en su representacin mediante grafo. As mismo se mostrar que, para ciertas topologas del grafo,