¿Qué problemas de SAT son fáciles?

27

¿Qué son las "regiones fáciles" para la satisfacción? En otras palabras, condiciones suficientes para que un solucionador de SAT pueda encontrar una tarea satisfactoria, suponiendo que exista.

Un ejemplo es cuando cada cláusula comparte variables con algunas otras cláusulas, debido a la prueba constructiva de LLL, ¿algún otro resultado en ese sentido?

Hay literatura considerable sobre regiones fáciles para la Propagación de creencias, ¿hay algo en ese sentido para la satisfacción?

Yaroslav Bulatov
fuente
2
¿también te interesa la transición aleatoria de la fase SAT?
Suresh Venkat
¿Cómo se ve la condición suficiente? Peter Shor mencionó en otra publicación que la instancia SAT necesita poseer una "estructura aleatoria" para hacer que la relación de cláusulas a variables sea relevante. Me pregunto si esto es algo que puede codificarse en condiciones suficientes
Yaroslav Bulatov

Respuestas:

33

Supongo que conoces el resultado clásico de Schaefer de STOC'78, pero por las dudas.

10.1145 / 800133.804350

Schaefer demostró que si SAT está parametrizado por un conjunto de relaciones permitidas en cualquier caso, entonces solo hay 6 casos manejables: 2-SAT (es decir, cada cláusula es binaria), Horn-SAT, dual-Horn-SAT, affine-SAT ( soluciones a ecuaciones lineales en GF (2)), 0-válido (relaciones satisfechas por la asignación all-0) y 1-válido (relaciones satisfechas por la asignación all-1).

Standa Zivny
fuente
3
Hay un artículo más reciente que refina este resultado: La complejidad de los problemas de satisfacción: "Refinando el teorema de Schaefer" Eric Allender, Michael Bauland, Neil Immerman, Henning Schnoor y Heribert Vollmer
Vinicius dos Santos
1
Gracias, aquí está el doi: dx.doi.org/10.1016/j.jcss.2008.11.001
Standa Zivny
Tenga en cuenta que estos son problemas de satisfacción de restricciones y no SAT (aunque pueden reescribirse como instancias SAT, pero técnicamente, SAT significa CSP con predicados OR).
MCH
14

No estoy seguro de si esto es lo que está buscando, pero hay una literatura considerable sobre la transición de la fase 3-SAT.

Monasson, Zecchina, Kirkpatrcik, Selman y Troyansky tenían un artículo en la naturaleza que habla sobre la transición de fase de k-SAT aleatorio. Utilizaron una parametrización de la razón de cláusulas a variables. Para el 3-SAT aleatorio, encontraron numéricamente que el punto de transición es alrededor de 4.3. Por encima de este punto, las instancias aleatorias de 3-SAT están demasiado restringidas y casi seguramente son inviables y, por debajo de este punto, los problemas están bajo restricciones y son satisfactorios (con alta probabilidad). Mertens, Mezard y Zecchina utilizan procedimientos de método de cavidad para estimar el punto de transición de fase a un mayor grado de precisión.

Lejos del punto crítico, los algoritmos "tontos" funcionan bien para instancias satisfactorias (walk sat, etc.). Por lo que entiendo, los tiempos de ejecución del solucionador determinista crecen exponencialmente en la transición de fase o cerca de ella (ver aquí para más información).

Primo cercano de la propagación de creencias, Braunstein, Mezard y Zecchina han introducido la propagación de encuestas que, según se informa, resuelve instancias satisfactorias de 3-SAT en millones de variables, incluso extremadamente cerca de la transición de fase. Mezard tiene una conferencia aquí sobre gafas giratorias (la teoría de la cual ha utilizado en el análisis de transiciones de fase NP-Completas aleatorias) y Maneva tiene una conferencia aquí sobre propagación de encuestas.

Desde la otra dirección, todavía parece que nuestros mejores solucionadores tardan una cantidad exponencial de tiempo para demostrar su insatisfacción. Vea aquí , aquí y aquí para obtener pruebas / discusión sobre la naturaleza exponencial de algunos métodos comunes para demostrar la insatisfacción (procedimientos de Davis-Putnam y métodos de resolución).

Hay que tener mucho cuidado con las afirmaciones de 'facilidad' o 'dureza' para problemas aleatorios de NP-Complete. Tener un problema NP-Complete muestra una transición de fase que no garantiza dónde están los problemas difíciles o si hay alguno. Por ejemplo, el problema del ciclo de Hamiltoniain en los gráficos aleatorios de Erdos-Renyi es demostrablemente fácil incluso en o cerca del punto crítico de transición. El problema de partición numérica no parece tener ningún algoritmo que lo resuelva bien en el rango de probabilidad 1 o 0, y mucho menos cerca del umbral crítico. Por lo que entiendo, los problemas aleatorios de 3-SAT tienen algoritmos que funcionan bien para instancias satisfactorias casi en o por debajo del umbral crítico (propagación de la encuesta, walk sat, etc.) pero no hay algoritmos eficientes por encima del umbral crítico para demostrar la insatisfacción.

usuario834
fuente
Me pregunto si esos resultados de "k-SAT aleatorio" se transfieren a instancias de SAT de la vida real, en otras palabras, si la relación de cláusulas a variables sigue siendo un indicador útil de dureza
Yaroslav Bulatov
1
@Yaroslav, desde mi experiencia, no. Muchos problemas del mundo real (incluso reducciones) tienen (o introducen) tanta estructura como para destruir la aleatoriedad para la que se han optimizado muchos solucionadores. Parece que en algún momento podríamos dar cuenta de esa estructura de alguna manera y ser capaces de enfocarnos solo en la porción de aleatoriedad (o la 'esencia' del problema aleatorio) pero no veo ninguna forma general de hacerlo ni ¿Conozco realmente algún ejemplo que emplee esa estrategia?
user834
R(F)Fr[0,1]F
5

Hay muchas condiciones suficientes. En cierto sentido, gran parte de la CS teórica se ha dedicado a la recopilación de estas condiciones: trazabilidad de parámetros fijos, 2-SAT, 3-SAT aleatorios de diferentes densidades, etc.

Peter Boothe
fuente
2
Es cierto, uno podría tomar cualquier problema X que sea fácil de resolver y decir que "cualquier fórmula que corresponda al problema X es fácil". Supongo que estoy buscando condiciones suficientes que sean más eficientes para resumir la región fácil que "todos los problemas que se sabe que están en P", más como lo que hace el constructivo Lovasz Local Lemma
Yaroslav Bulatov
3

No existe un reconocimiento generalizado de este concepto hasta ahora en la literatura, pero el gráfico de cláusula del problema SAT (el gráfico con un nodo por cláusula y los nodos están conectados si las cláusulas comparten variables), así como otros gráficos relacionados de la representación SAT, parece tener muchas pistas básicas sobre cuán difícil será la instancia en promedio.

El gráfico de la cláusula se puede analizar a través de todo tipo de algoritmos teóricos de gráficos, es una medida aparentemente natural de "estructura" y con fuertes conexiones para medir / estimar la dureza, y parece que la investigación de esta estructura y sus implicaciones aún es muy temprana. etapas No es inconcebible que la investigación del punto de transición, una / la forma tradicional y bien estudiada de abordar esta cuestión, pueda incorporarse a esta estructura gráfica de cláusulas (hasta cierto punto, ya lo ha hecho). en otras palabras, se puede ver que el punto de transición en SAT existe "debido a" la estructura del gráfico de la cláusula.

Aquí hay una excelente referencia en este sentido, una tesis doctoral de Herwig, hay muchas otras.

[1] Descomponiendo problemas de satisfacción o Utilizando gráficos para obtener una mejor visión de los problemas de satisfacción , Herwig 2006 (83pp)

vzn
fuente
Este es el gráfico de dependencia cuando se aplica el lema local lovasz y las variantes a la satisfacción. en ese sentido, el gráfico de la cláusula se ha mirado mucho . Shearer caracteriza los gráficos para los que se mantiene el lema local, y Kolipaka y Szegedy han hecho que el resultado de Schaefer sea constructivo. Cuando no sepas mucho, por favor, ¡no deduzcas que nadie lo sabe!
Sasho Nikolov
El desglose de shaefers en algunas clases manejables se menciona en la respuesta de Zivny, pero este análisis gráfico de cláusulas es relativamente más nuevo, más profundo y más matizado, y más con un sabor empírico. En cuanto a las citas que menciona, no parece que se mencione a menudo en los documentos / investigaciones de dureza del SAT ... hay líneas de investigación múltiples / paralelas entrelazadas ...
vzn
Schaefer era un error tipográfico, me refería a Shearer. LLL y ​​sus variantes son una herramienta principal para delimitar las instancias difíciles de k-SAT, una búsqueda en Google revelará toneladas de referencias. El teorema de Shearer muestra qué gráficos de cláusulas garantizan que cualquier instancia de SAT con ese gráfico es necesariamente satisfactoria. Mire esta encuesta para conexiones detalladas a umbrales de dureza, dificultad para construir instancias difíciles, algoritmos, etc. disco.ethz.ch/lectures/fs11/seminar/paper/barbara-3.pdf
Sasho Nikolov
1
un pensamiento general: cada vez que dices algo es terra incógnita, existe una gran posibilidad de que sea terra incógnita para ti . en cualquier caso, este tipo de comentario es inútil a menos que sea un experto establecido y publicado en el área. Sería mejor si restringiera sus respuestas a lo que sabe y omita comentarios sobre lo que cree que nadie sabe.
Sasho Nikolov
1
LLL es una herramienta para analizar SAT, inventada en 1975 con quizás algunos refinamientos desde entonces. es una receta para suficientes instancias fáciles o difíciles, pero no es necesario . existen otros enfoques desde entonces que llenan cada vez más el vacío de formas novedosas, es decir, lo amplían y lo evitan. debe confundir esta respuesta con otra cosa, no hay uso del término "terra incognita" en la pregunta anterior. Y sugiere que se confine a las respuestas escritas reales y no especular acerca de lo que otros saben o habilidades Dont =)
VZN
1

Es fácil mover todas las instancias cerca del punto de "transición" tan lejos del punto de "transición" como se desee. El movimiento implica un esfuerzo de tiempo / espacio polinómico.

Si las instancias lejos del punto de "transición" son más fáciles de resolver, entonces aquellas cercanas al punto de transición deben ser igualmente fáciles de resolver. (Transformaciones polinomiales y todo).

GHR
fuente
¿Puedes dar más detalles o tienes una referencia para esto?
vzn
1

κ

encuentra una aparente estructura de auto-similitud fractal de instancias duras con el parámetro restrictor de modo que, como solucionador de DP (LL) durante la búsqueda, tiende a encontrar subproblemas con la misma restricción crítica, sin importar qué variable se elija al lado de la ramificación. Hay algunos análisis adicionales de la estructura fractal en las instancias SAT (como la dimensión de Hausdorff de las fórmulas SAT y la conexión a la dureza) en, por ejemplo, [2,3]

Otra línea de investigación algo interrelacionada aquí es la relación de los gráficos de mundo pequeño con la estructura SAT (dura), p. ej. [4,5]

=?

[1] El límite del cuchillo de restricción por Toby Walsh 1998

[2] SIMILARIDAD DE LAS EXPRESIONES BOOLEAS SATISFIABLES DECIFERADAS EN TÉRMINOS DE SISTEMAS DE FUNCIONAMIENTO ITERADOS DIRIGIDOS GRÁFICOS por Ni y Wen

[3] Visualización de la estructura interna de las instancias SAT (Informe preliminar) Sinz

[4] Búsqueda en un mundo pequeño por Walsh 1999

[5] Modelando problemas SAT más realistas por Slater 2002

vzn
fuente
3
Es DPLL, no DP (LL) por cierto. Además, hay un trabajo significativamente más reciente sobre la transición de fase en SAT (ver el trabajo de Achlioptas, por ejemplo).
Vijay D
Hay un algoritmo DP que precede a DPLL que tiene un comportamiento similar. la otra respuesta del usuario834 mencionó principalmente la investigación del punto de transición SAT con muchas referencias, pero esta respuesta enfatiza un ángulo diferente (pero interrelacionado)
vzn
1
Soy consciente de estos algoritmos. Solo estaba señalando la convención tipográfica estándar, que es escribir DP, o DPLL, o DPLL (T), o DPLL (Unir), para el caso de primer orden libre de cuantificadores. Nadie escribe DP (LL) y agrega confusión con DPLL (T) y DPLL (Join)
Vijay D
DP (LL) es lo que se entiende como DP + DPLL
vzn