Contador de tiempo polinomial de soluciones de 2sat expresión con literales puros.

Question

Según el título, ¿existe algún algoritmo de tiempo polinomial para contar el número de argumentos satisfactorios para una expresión 2SAT con literales puros?Un caso aún menos profunda: ¿Hay algún contador de este tipo cuando los literales en la expresión son todos positivos, o todos negativos?

Answer 1

Contando el número de asignaciones satisfactorias en una fórmula positiva de 2SAT es la misma que contar el número de cubiertas de vértices en el gráfico correspondiente (después de eliminar las cláusulas de Singleton).Se sabe que contar el número de cubiertas de vértice es $ \ mathsf {\ # p} $ -clete.Consulte también esta pregunta en CSTHEORY.