¿Hay un algoritmo a veces eficiente para resolver #SAT?

Sea una fórmula booleana que consta de los operadores habituales AND, OR y NOT y algunas variables. Me gustaría contar el número de asignaciones para satisfacer . Es decir, quiero encontrar el número de asignaciones diferentes de valores de verdad a las variables de para las cuales asume un valor verdadero. Por ejemplo, la fórmula tiene tres asignaciones satisfactorias; tiene cuatro. Este es el problema #SAT . $B$ $B$ $B$ $B$ $a\lor b$ $(a\lor b)\land(c\lor\lnot b)$

Obviamente, una solución eficiente para este problema implicaría una solución eficiente para SAT, lo cual es poco probable, y de hecho este problema es # P-completo, por lo que bien podría ser estrictamente más difícil que SAT. Por lo tanto, no espero una solución garantizada y eficiente.

Pero es bien sabido que hay relativamente pocos casos realmente difíciles de SAT en sí. (Véase, por ejemplo, Cheeseman 1991, "Donde están los problemas realmente difíciles" ). La búsqueda podada ordinaria, aunque exponencial en el peor de los casos, puede resolver muchos casos de manera eficiente; Los métodos de resolución, aunque exponenciales en el peor de los casos, son aún más eficientes en la práctica.

Mi pregunta es:

¿Se conocen algoritmos que puedan contar rápidamente el número de asignaciones satisfactorias de una fórmula booleana típica, incluso si dichos algoritmos requieren un tiempo exponencial en la instancia general? ¿Hay algo notablemente mejor que enumerar todas las asignaciones posibles?

complexity-theory reference-request satisfiability Mark Dominus
fuente

Intenté agregar una etiqueta para # p-completeness, pero al software Stack Exchange no le gusta el signo #.

Mark Dominus el

k

$k$

Gracias. ¿Crees que esto tiende a aclarar mi pregunta? ¿Entiendes lo que te pido?

Mark Dominus el

Me queda claro. Solo es importante recordar qué instancias exhiben la transición de fase :)

Juho

Respuestas:

Contando en el caso general

$2$

Los métodos de conteo exactos a menudo se basan en una búsqueda exhaustiva de estilo DPLL o en algún tipo de compilación de conocimiento. Los métodos aproximados generalmente se clasifican como métodos que ofrecen estimaciones rápidas sin garantías y métodos que proporcionan límites inferiores o superiores con una garantía de corrección. También hay otros métodos que podrían no ajustarse a las categorías, como descubrir puertas traseras, o métodos que insisten en ciertas propiedades estructurales para mantener las fórmulas (o su gráfico de restricción).

Hay implementaciones prácticas por ahí. Algunos contadores de modelos exactos son CDP, Relsat, Cachet, sharpSAT y c2d. El tipo de técnicas principales utilizadas por los solucionadores exactos son conteos parciales, análisis de componentes (del gráfico de restricción subyacente), almacenamiento en caché de fórmulas y componentes, y razonamiento inteligente en cada nodo. Otro método basado en la compilación de conocimiento convierte la fórmula CNF de entrada en otra forma lógica. De esta forma, el recuento del modelo se puede deducir fácilmente (tiempo polinómico en el tamaño de la fórmula recién producida). Por ejemplo, uno podría convertir la fórmula en un diagrama de decisión binario (BDD). Entonces se podría atravesar el BDD desde la hoja "1" hasta la raíz. O para otro ejemplo, el c2d emplea un compilador que convierte las fórmulas CNF en una forma normal de negación determinista descomponible (d-DNNF).

$\phi$ $\phi$

Gogate y Dechter [3] usan una técnica de conteo modelo conocida como SampleMinisat. Se basa en el muestreo del espacio de búsqueda sin retroceso de una fórmula booleana. La técnica se basa en la idea de volver a muestrear la importancia, utilizando solucionadores SAT basados en DPLL para construir el espacio de búsqueda sin retroceso. Esto puede hacerse completamente o hasta una aproximación. También es posible el muestreo de estimaciones con garantías. Sobre la base de [2], Gomes et al. [4] mostró que usando el muestreo con una estrategia aleatoria modificada, uno puede obtener límites inferiores demostrables en el recuento total del modelo con altas garantías de corrección probabilística.

También hay trabajo que se basa en la propagación de creencias (BP). Ver Kroc et al. [5] y el BPCount que presentan. En el mismo documento, los autores dan un segundo método llamado MiniCount, para proporcionar límites superiores en el recuento de modelos. También hay un marco estadístico que permite calcular los límites superiores bajo ciertas suposiciones estadísticas.

Algoritmos para # 2-SAT y # 3-SAT

$O(1.3247^n)$ $O(1.6894^n)$ $O(1.6423^n)$

Como está en la naturaleza del problema, si desea resolver instancias en la práctica, mucho depende del tamaño y la estructura de sus instancias. Cuanto más sepa, más capaz será para elegir el método correcto.

[1] Vilhelm Dahllöf, Peter Jonsson y Magnus Wahlström. Contando asignaciones satisfactorias en 2-SAT y 3-SAT. En Actas de la VIII Conferencia Anual Internacional de Computación y Combinatoria (COCOON-2002), 535-543, 2002.

[2] W. Wei y B. Selman. Un nuevo enfoque para el conteo de modelos. En Proceedings of SAT05: 8th International Conference on Theory and Applications of Satisfiability Testing, volumen 3569 de Lecture Notes in Computer Science, 324-339, 2005.

[3] R. Gogate y R. Dechter. Recuento aproximado mediante el muestreo del espacio de búsqueda sin retroceso. En Actas de AAAI-07: 22ª Conferencia Nacional sobre Inteligencia Artificial, 198–203, Vancouver, 2007.

[4] CP Gomes, J. Hoffmann, A. Sabharwal y B. Selman. Del muestreo al conteo de modelos. En Actas de IJCAI-07: XX Conferencia Internacional Conjunta sobre Inteligencia Artificial, 2293–2299, 2007.

[5] L. Kroc, A. Sabharwal y B. Selman. Aprovechar la propagación de creencias, la búsqueda de retroceso y las estadísticas para el conteo de modelos. En CPAIOR-08: 5ª Conferencia internacional sobre integración de técnicas de IA y OR en la programación de restricciones, volumen 5015 de Lecture Notes in Computer Science, 127–141, 2008.

[6] K. Kutzkov. Nuevo límite superior para el problema # 3-SAT. Information Processing Letters 105 (1), 1-5, 2007.

Juho
fuente

Además de los documentos enumerados por Juho, aquí hay algunos otros que describen el trabajo sobre este tema, especialmente en la aproximación del número de soluciones:

Modelo de conteo . Carla P. Gomes, Ashish Sabharwal, Bart Selman Handbook of Satisfiability, IOS Press. Editores: Armin Biere, Marijn Heule, Hans van Maaren y Toby Walsh. Capítulo 20, pp 633-654, 2009.
- Esto tiene una buena visión general del tema y una introducción a una serie de técnicas.
Muestreo casi uniforme de espacios combinatorios utilizando restricciones XOR . Carla P. Gomes, Ashish Sabharwal, Bart Selman. NIPS-06. XX Conferencia Anual sobre Sistemas de Procesamiento de Información Neural, pp 481-488, Vancouver, BC, Canadá, diciembre de 2006.
XOR cortos para el conteo de modelos: de la teoría a la práctica . Carla P. Gomes, Joerg Hoffmann, Ashish Sabharwal, Bart Selman SAT-07. Décima Conferencia Internacional sobre Teoría y Aplicaciones de Pruebas de Satisfacción, LNCS volumen 4501, pp 100-106, Lisboa, Portugal, mayo de 2007.
Aprovechar la propagación de creencias, la búsqueda de retroceso y las estadísticas para el conteo de modelos . Lukas Kroc, Ashish Sabharwal, Bart Selman ANOR-2011. Annals of Operations Research, volumen 184, número 1, pp 209-231, 2011.
Heurística para el conteo rápido de modelos exactos . Tian Sang, Paul Beame y Henry Kautz. Teoría y aplicaciones de las pruebas de satisfacción (SAT 2005), pp 226-240.

DW
fuente