Mejores límites superiores en SAT

43

En otro hilo , Joe Fitzsimons preguntó sobre "los mejores límites inferiores actuales en 3SAT".

Me gustaría ir a otro lado: ¿Cuál es el mejor límite superior actual en 3SAT? En otras palabras, ¿cuál es la complejidad temporal del solucionador SAT más eficiente?

En particular, ¿es concebible encontrar un algoritmo sub-exponencial (pero super-polinomial) para SAT?

cc.complexity-theory ds.algorithms sat upper-bounds MS Dousti
fuente

2

No sé acerca de los resultados analíticos, pero puede encontrar resultados experimentales aquí baldur.iti.uka.de/sat-race-2010/results.html (vea los enlaces "HTML")

Radu GRIGore

1

el título de esta pregunta es un poco engañoso, debido a la existencia de esta pregunta: cstheory.stackexchange.com/questions/1295/sat-solver-download . ¿Creo que podría reformularse como 'Mejores límites superiores en SAT'?

Suresh Venkat

@Suresh: La pregunta a la que se refiere se refiere a "#SAT", mientras que esta corresponde a SAT. Además, se hizo esa pregunta aproximadamente una semana después de esta. De todos modos, ¿todavía sugieres cambiar el título de este?

MS Dousti

sí, porque un "SAT Solver" es un objeto específico bien conocido, una base de código real para resolver SAT. Google se confundirá y redirigirá a las personas que buscan código aquí :).

Suresh Venkat

44

Con respecto a la motivación para esta pregunta, pensé que varias personas habían probado los solucionadores SAT en las instancias de 17x17. Parece ser la frontera de lo que se puede manejar con un solucionador SAT. En su lugar, podría intentar un solucionador paralelo, pero tenía la impresión, según las publicaciones de Bill Gasarch, de que necesitaría un esfuerzo a gran escala. También puede aplicar un solucionador SMT con una teoría adecuada, o utilizar un solucionador de restricciones que implemente una restricción global que tenga un propagador eficiente. En cada uno de estos casos, la nueva idea sería expresar una propiedad importante que es difícil de hacer usando cláusulas.

András Salamon

38

Hay dos tipos de "mejores" solucionadores SAT, uno para teoría y otro para práctica.

Teoría

Kazuo Iwama, Kazuhisa Seto, Tadashi Takai, Suguru Tamaki, " Algoritmos aleatorios mejorados para 3-SAT ", ISAAC 2010.

aleatorizado para 3SAT. $O(1.32113^n)$

Timon Hertli, Robin A. Moser, Dominik Scheder, " Mejora de PPSZ para 3-SAT utilizando variables críticas ", 2011.

aleatorizado para 3SAT. $O(1.321^n)$

Konstantin Kutzkov, Dominik Scheder, " Uso de CSP para mejorar el 3-SAT determinista ", 2010.

determinista para 3SAT. $O(1.439^n)$

Práctica

Consulte la conferencia SAT para ver los resultados de la competencia de cada año.

Tian Liu
fuente

Encontré un enlace a Iwama et al. papel . Entonces, ¿es

realmente el último y mejor resultado para resolver SAT hasta ahora?

O ({1.32113}^{n})

$O(1.32113^n)$

MS Dousti

@ Sadeq: Creo que sí, pero solo para 3-SAT, no SAT.

Tian Liu

2

Ahora el mejor algoritmo está en tiempo

de Timon Hertli, Robin A. Moser y Dominik Scheder.

O ({1.321}^{n})

$O(1.321^n)$

Tian Liu

10

Otra actualización más: en FOCS 2011, Timon Hertli ( arxiv.org/abs/1103.2165 ) demostró que el algoritmo PPSZ resuelve cada instancia de 3SAT en

veces.

{1.308}^{n}

$1.308^n$

Ryan Williams

21

No conozco ningún algoritmo aleatorio de error cero (o algoritmos coNE / Eadvice ,
para el caso) para SAT que tenga mejores límites que los algoritmos deterministas conocidos,
independientemente de si se promete o no una asignación satisfactoria.

Desrandomizar el algoritmo HSSW para 3-SAT muestra que

"El problema 3-SAT se puede resolver determinísticamente en el tiempo ". $\overset{\sim}{O}(1.3303^n)$

La desrandomización de PPSZ para Unique-k-SAT muestra que:

"Para un 3-CNF excepcionalmente satisfactorio (resp. 4-CNF) en variables, la asignación satisfactoria se puede encontrar en el tiempo de ejecución determinista como máximo $n$
(resp. $O\hspace{.02 in}(1.3071^n)$ ) ". $O\hspace{.02 in}(1.4699^n)$

3-SAT más rápido y más simple: los límites únicos de SAT para PPSZ Hold en general muestran que (originalmente mencionado en el comentario de Ryan )

"Existe un algoritmo aleatorio para 3-SAT con
error unilateral que se ejecuta en el tiempo ". $O\hspace{.02 in}(1.30704^n)$

"Existe un algoritmo aleatorio para 4-SAT con
error unilateral que se ejecuta en el tiempo ". $O\hspace{.02 in}(1.46899^n)$

Romper la barrera PPSZ para Unique 3-SAT
reclama un resultado que se puede resumir de la siguiente manera:

"Hay un algoritmo aleatorio para unique-3-SAT tal que para $\: \epsilon = 1\hspace{-0.03 in}\big/\hspace{-0.06 in}\left(\hspace{-0.03 in}10^{\hspace{.02 in}24}\hspace{-0.04 in}\right) \:$ y
el número real que permite que el tiempo de ejecución del trabajo anterior para 3-SAT se exprese como $S$
$\: O\hspace{-0.04 in}\left(2^{(S+o(1))\cdot n}\right) \:$ , $\;$ el algoritmo del trabajo actual se ejecuta a tiempo ". $\: O\hspace{-0.04 in}\left(2^{(S-\epsilon+o(1))\cdot n}\right)$

Comunidad
fuente

16

El algoritmo de Schoening es un algoritmo probabilístico para k-SAT con tiempo de ejecución , donde . Esto da como resultado un algoritmo para 3SAT, un $O(a^n)$ $a = 2(k-1)/k$ $O(1.33334^n)$ $O(1.5^n)$ para 4SAT, etc.

El algoritmo también ha sido (casi completamente) desrandomizado por Moser y Scheder, quienes dan un algoritmo determinista para resolver el tiempo de ejecución de kSAT donde es la misma constante que antes, y $O((a+\epsilon)^n)$ $a$ $\epsilon>0$ se puede hacer arbitrariamente pequeño

Nota: En esta respuesta, la gran notación Oh oculta los factores poli (n). Quería usar la notación , pero no se procesa correctamente. $O^*$

Robin Kothari
fuente

1

¿Por qué dices "casi por completo"? ¿Me perdí algo en el periódico?

András Salamon

1

Hay un

determinista

algoritmo para k-SAT de ocho personas, así que perdóneme sin mencionarlos a todos. Aquí está el enlace:linkshub.elsevier.com/retrieve/pii/S0304397501001748. Entonces, para

tenemos

y no es tan bueno como otros límites para 3-SAT presentados aquí, pero para k-SAT es el mejor, que yo sepa.

O ((2 - \frac{2}{k + 1})^{n})

$O((2 - \frac{2}{k + 1})^n)$

k = 3

$k = 3$

O ({1.5}^{n})

$O(1.5^n)$

Grigory Yaroslavtsev

44

Dije "casi por completo" solo para indicar que hay un factor épsilon allí. Supongo que uno esperaría que una desrandomización completa logre el mismo tiempo de ejecución (hasta factores polinomiales). O tal vez eso no sea razonable esperar.

Robin Kothari

1

@Grigory Yaroslavtsev: ¿No es el algoritmo determinista Moser-Scheder para kSAT que mencioné más rápido que el que usted citó? ¿Me estoy perdiendo de algo?

Robin Kothari

1

Estaba preocupado por esto

en tu notación, por lo que es más rápido. Parece que el artículo apareció en arXiv hace solo unos días: arxiv.org/PS_cache/arxiv/pdf/1008/1008.4067v1.pdf , así que no me sorprende que no lo supiera.

ϵ

$\epsilon$

Grigory Yaroslavtsev

12

Como ya se mencionó, si está interesado en las garantías teóricas de tiempo de ejecución, esta pregunta es un duplicado.

Pero me gustaría señalar que si realmente desea resolver un problema concreto (como el problema de coloración que mencionó), creo que no tiene absolutamente ningún sentido estudiar los límites superiores teóricos.

Aunque deseaba evitar los aspectos de "ingeniería", le sugiero que tome algunos solucionadores SAT populares, los pruebe y vea qué sucede (la mayoría de ellos pueden leer el mismo formato de archivo DIMACS, por lo que es fácil intentarlo diferentes solucionadores). Puede tener sorpresas positivas y negativas. Recientemente tuve una familia de instancias SAT; Un montón de instancias con decenas de miles de variables y más de un millón de cláusulas resultaron fáciles de resolver, mientras que las instancias aparentemente mucho más simples con solo cientos de variables y miles de cláusulas fueron demasiado difíciles para cualquier solucionador que intenté.

Jukka Suomela
fuente

8

Además del resumen de Jukka, también vale la pena señalar que hay dos tipos principales de solucionadores de SAT: aquellos basados en la propagación de encuestas, que funcionan bien para instancias de SAT aleatorias, y aquellos que usan el aprendizaje de cláusulas combinado con la resolución de la unidad, que tienden a funcionar bien descubrir estructura combinatoria. Estos tienen un comportamiento bastante diferente. Los peores casos para los solucionadores de SAT tienden a ser instancias que no son satisfactorias, pero donde el espacio de nogoods tiene una estructura compleja que no permite muchas podas. Lamentablemente, los casos de combinatoria tienden a ser de este tipo.

András Salamon

11

Timon Hertli, " 3-SAT más rápido y más simple - Límites únicos-SAT para PPSZ Hold en general ", FOCS 2011.

$O(1.308^n)$

Kaveh
fuente

Supongo que cuando a alguien se le ocurre un límite superior mejor, citaría este artículo. Solo se ha citado una vez este documento, que es "Un algoritmo de satisfacción y dureza promedio de mayúsculas y minúsculas para fórmulas sobre la base binaria completa". Y parecen hablar solo de ciertos tipos de fórmulas. Por lo tanto, este parece ser el mejor límite superior hasta ahora.

Tayfun paga

@TayfunPay:

$\:$ El último papel en mi respuesta cita ese papel.

$\;\;\;\;$

@RickyDemer Uhuh! ¿Es un límite mejor que esto? La notación no es tan clara para mí.

Tayfun paga

@TayfunPay:

$\:$ Sí, y puede buscar en los dos documentos como se describe a continuación.

$\:$

S_{3}

$S_3$

S_{k}

$S_k$

$\:$ En la parte superior de la página 11, ese documento dice que su algoritmo tiene el mismo límite que PPSZ, lo que significa que no mostraron nada más de lo que mencioné en mi oración anterior.

$\:$ (continúa ...)

$\hspace{.35 in}$

(... continuación)

$\:$

S

$S$

2^{S \cdot n}

$2^{S\cdot n}$

$\:$

S

$S$

S_{3}

$S_3$

$\;\;\;$

8

Es imposible que 3SAT tenga algoritmos sub-exponenciales a menos que la hipótesis del tiempo exponencial sea falsa.

Kazuo Iwama, Suguru Tamaki, límites superiores mejorados para 3-SAT , 2004.

$O({1.324}^n)$

Daniel Rolf, Mejorado Bound para el algoritmo PPSZ / Schoning para 3-SAT , 2005.

$O({1.32216}^n)$

Mohammad Al-Turkistany
fuente

15

¿No es eso una tautología?

Tsuyoshi Ito

1

2^{o (n)}

$2^{o(n)}$

El trabajo de Kazuo Iwama et al. (2004) es más nuevo que el de Schoening (1999). Me pregunto si hay resultados aún más recientes disponibles.

MS Dousti

8

Para evitar la posibilidad de confusión, mi último comentario se refiere a la primera oración de la respuesta: "Es imposible que 3SAT tenga algoritmos sub-exponenciales a menos que la hipótesis del tiempo exponencial (ETH) sea falsa". Entiendo que el tiempo exponencial La hipótesis es la misma hipótesis que establece que no hay un algoritmo para 3SAT cuyo tiempo de ejecución sea subexponencial (es decir, 2 ^ {o (n)}) en el número de variables.

Tsuyoshi Ito

10

Y para evitar más confusión, agregaré que cuando Tsuyoshi publicó su comentario, la respuesta solo contenía esa oración, lo que hizo que su comentario fuera muy apropiado.

Robin Kothari

7

Esta publicación trata de los límites superiores en SAT. Este uno se ocupa de mejores cotas inferiores. Este enlace brinda detalles de la competencia anual que compara las implementaciones de solucionadores SAT, que se pueden descargar. Para simplificar, puede comenzar con SAT4J , una biblioteca basada en Java para la resolución de SAT.

Dave Clarke
fuente

Resulta que esta cuestión fue ya le han hecho antes; Simplemente no lo vi cuando busqué en el sitio web. La respuesta de Tian Liu en la pregunta de los límites superiores es exactamente lo que estaba buscando. Gracias por los enlaces, Dave!

Daniel Apon

1

Esto es evidencia de que paso mucho tiempo aquí ;-)

Dave Clarke

estamos contentos de que lo hagas :)

Suresh Venkat

2

No estoy seguro de si recomendaría sat4J, no solo es significativamente más lento que el estado de la técnica, sino también algo más complejo. Sin embargo, es cierto que es muy personalizable debido a la estructura orientada a objetos. MiniSat está muy bien escrito y 2.2 es de última generación.

Mikolas

3

El mejor algoritmo determinista para 3-SAT ahora tiene un límite superior 1.32793 ^ n, consulte https://arxiv.org/abs/1804.07901 de Sixue Liu. Básicamente, los límites superiores para todos los k-SAT se han mejorado en este documento.

EN KI Wong
fuente

Mejores límites superiores en SAT

Respuestas:

Teoría

Práctica