2-satisfacibilidad problema si existe una asignación de verdad única o no

Question

Tengo un problema que es una extensión de un problema 2-SAT. En la norma problema 2-SAT, podemos encontrar cualquiera de las asignaciones de verdad que depende de la orden de los vértices que elegimos. Quiero comprobar si existe una y sólo una asignación de verdad (es decir, sólo una combinación) para el que la expresión es satisfiable. El número de literales puede ser 100.000. Una forma es encontrar todas las posibles asignaciones de verdad, luego compararlas si son distintos. Pero el problema es que cada comparación, voy a tener que comparar los valores 100000 (no de literales). ¿Hay alguna forma eficiente?

Answer 1

Feder (1994) describe un algoritmo para la lista de manera eficiente todas las soluciones a un determinado 2- ejemplo satisfacibilidad . También hay citas en el artículo para algoritmos para contar el número de asignaciones, pero sólo se necesitan intentar lista dos asignaciones, que puede ser más eficiente.