Hispanopedia Wiki
Articulo de referencia

solucionador SAT

En informática y métodos formales , un solucionador SAT es un programa informático que busca resolver el problema de satisfacibilidad booleana (SAT). Al introducir una fórmula s...

Hispanopedia WikiContenido en espanolLectura gratuita

En informática y métodos formales , un solucionador SAT es un programa informático que busca resolver el problema de satisfacibilidad booleana (SAT). Al introducir una fórmula sobre variables booleanas , como "( x o y ) y ( x o no y )", un solucionador SAT indica si la fórmula es satisfacible , es decir, si existen valores posibles de x e y que la hacen verdadera, o insatisfacible, es decir , si no existen tales valores . En este caso, la fórmula es satisfacible cuando x es verdadera, por lo que el solucionador debería devolver "satisfacible". Desde la introducción de algoritmos para SAT en la década de 1960, los solucionadores SAT modernos se han convertido en complejos programas que incorporan numerosas heurísticas y optimizaciones para funcionar de manera eficiente.

Según el teorema de Cook-Levin , la satisfacibilidad booleana es, en general, un problema NP-completo . Por consiguiente, solo se conocen algoritmos con complejidad exponencial en el peor de los casos. A pesar de ello, durante la década de 2000 se desarrollaron algoritmos eficientes y escalables para SAT, que contribuyeron a avances significativos en la capacidad de resolver automáticamente instancias de problemas con decenas de miles de variables y millones de restricciones. [ 1 ]

Los solucionadores SAT suelen comenzar convirtiendo una fórmula a su forma normal conjuntiva . Generalmente se basan en algoritmos básicos como el algoritmo DPLL , pero incorporan diversas extensiones y características. La mayoría de los solucionadores SAT incluyen tiempos de espera, por lo que finalizan en un tiempo razonable incluso si no encuentran una solución, con una salida como "desconocido" en este último caso. A menudo, los solucionadores SAT no solo proporcionan una respuesta, sino que también ofrecen información adicional, como una asignación de ejemplo (valores para x , y , etc.) si la fórmula es satisfacible, o un conjunto mínimo de cláusulas insatisfacibles si la fórmula no lo es.

Los solucionadores SAT modernos han tenido un impacto significativo en campos como la verificación de software , el análisis de programas , la resolución de restricciones , la inteligencia artificial , la automatización del diseño electrónico y la investigación operativa . Existen solucionadores potentes disponibles como software libre y de código abierto , e integrados en algunos lenguajes de programación, como la exposición de solucionadores SAT como restricciones en la programación lógica con restricciones .

Descripción general

Una fórmula booleana es cualquier expresión que se puede escribir utilizando variables booleanas (proposicionales) x, y, z, ... y las operaciones booleanas AND, OR y NOT. Por ejemplo,

( x Y y ) O ( x Y (NO z ))

Una asignación consiste en elegir, para cada variable, un valor VERDADERO o FALSO. Para cualquier asignación v , se puede evaluar la fórmula booleana, cuyo resultado es verdadero o falso. La fórmula es satisfacible si existe una asignación (denominada asignación satisfactora ) para la cual la fórmula resulta verdadera.

El problema de satisfacibilidad booleana es un problema de decisión que consiste en determinar, a partir de una fórmula booleana, si dicha fórmula es satisfacible o no. Este problema es NP-completo .

Algoritmos principales

Los solucionadores SAT suelen desarrollarse utilizando uno de dos enfoques principales: el algoritmo de Davis-Putnam-Logemann-Loveland (DPLL) y el aprendizaje de cláusulas basado en conflictos (CDCL).

DPLL

Un solucionador DPLL SAT emplea un procedimiento de búsqueda de retroceso sistemático para explorar el espacio (de tamaño exponencial) de asignaciones de variables buscando asignaciones satisfactorias. El procedimiento de búsqueda básico fue propuesto en dos artículos fundamentales a principios de la década de 1960 (ver referencias a continuación) y ahora se conoce comúnmente como el algoritmo DPLL . [ 2 ] [ 3 ] Muchos enfoques modernos para la resolución práctica de SAT se derivan del algoritmo DPLL y comparten la misma estructura. A menudo, solo mejoran la eficiencia de ciertas clases de problemas SAT, como instancias que aparecen en aplicaciones industriales o instancias generadas aleatoriamente. [ 4 ] Teóricamente, se han demostrado cotas inferiores exponenciales para la familia de algoritmos DPLL.

CDCL

Los solucionadores SAT modernos (desarrollados en la década de 2000) se presentan en dos variantes: "basados ​​en conflictos" y "anticipación". Ambos enfoques derivan de DPLL. [ 4 ] Los solucionadores basados ​​en conflictos, como el aprendizaje de cláusulas basado en conflictos (CDCL), amplían el algoritmo de búsqueda DPLL básico con análisis de conflictos eficiente, aprendizaje de cláusulas, retroceso , una forma de propagación de unidades de "literales de dos observadores" , ramificación adaptativa y reinicios aleatorios. Se ha demostrado empíricamente que estos "extras" a la búsqueda sistemática básica son esenciales para manejar las grandes instancias SAT que surgen en la automatización del diseño electrónico (EDA). [ 5 ] La mayoría de los solucionadores SAT de última generación se basan en el marco CDCL a partir de 2019. [ 6 ] Entre las implementaciones más conocidas se incluyen Chaff [ 7 ] y GRASP . [ 8 ]

Los solucionadores con anticipación han reforzado especialmente las reducciones (yendo más allá de la propagación de cláusulas unitarias) y las heurísticas, y generalmente son más fuertes que los solucionadores basados ​​en conflictos en instancias difíciles (mientras que los solucionadores basados ​​en conflictos pueden ser mucho mejores en instancias grandes que en realidad tienen una instancia fácil en su interior).

El MiniSAT basado en conflictos, que tuvo un éxito relativo en la competición SAT de 2005, solo tiene unas 600 líneas de código. Un solucionador SAT paralelo moderno es ManySAT. [ 9 ] Puede lograr aceleraciones superlineales en clases importantes de problemas. Un ejemplo de solucionadores con anticipación es march_dl, que ganó un premio en la competición SAT de 2007. El solucionador CP-SAT de Google, parte de OR-Tools , ganó medallas de oro en las competiciones de programación con restricciones Minizinc en ediciones de 2018 a 2025.

Ciertos tipos de instancias satisfacibles aleatorias de gran tamaño de SAT pueden resolverse mediante propagación de encuestas (SP). Particularmente en aplicaciones de diseño y verificación de hardware , la satisfacibilidad y otras propiedades lógicas de una fórmula proposicional dada a veces se deciden en función de una representación de la fórmula como un diagrama de decisión binario (BDD).

Los distintos solucionadores de SAT encontrarán diferentes instancias fáciles o difíciles, y algunos sobresalen en demostrar la insatisfacibilidad, mientras que otros lo hacen en encontrar soluciones. Todos estos comportamientos se pueden observar en los concursos de resolución de SAT. [ 10 ]

Enfoques paralelos

Los solucionadores SAT paralelos se dividen en tres categorías: cartera, divide y vencerás y algoritmos de búsqueda local paralelos . En las carteras paralelas, varios solucionadores SAT diferentes se ejecutan simultáneamente. Cada uno resuelve una copia de la instancia SAT, mientras que los algoritmos de divide y vencerás dividen el problema entre los procesadores. Existen diferentes enfoques para paralelizar los algoritmos de búsqueda local.

La Competencia Internacional de Solucionadores SAT tiene una pista paralela que refleja los avances recientes en la resolución paralela de SAT. En 2016, [ 11 ] 2017 [ 12 ] y 2018, [ 13 ] los puntos de referencia se ejecutaron en un sistema de memoria compartida con 24 núcleos de procesamiento , por lo que los solucionadores destinados a memoria distribuida o procesadores multinúcleo podrían no haber alcanzado el nivel esperado.

Portafolios

En general, no existe ningún solucionador SAT que supere a todos los demás solucionadores en todos los problemas SAT. Un algoritmo puede funcionar bien para instancias de problemas con las que otros tienen dificultades, pero tendrá un rendimiento inferior en otras instancias. Además, dada una instancia SAT, no existe una forma fiable de predecir qué algoritmo la resolverá con especial rapidez. Estas limitaciones motivan el enfoque de cartera paralela. Una cartera es un conjunto de algoritmos diferentes o configuraciones diferentes del mismo algoritmo. Todos los solucionadores de una cartera paralela se ejecutan en distintos procesadores para resolver el mismo problema. Si un solucionador finaliza, el solucionador de la cartera informa si el problema es satisfacible o insatisfacible según ese solucionador. Todos los demás solucionadores finalizan. La diversificación de las carteras mediante la inclusión de una variedad de solucionadores, cada uno con un buen rendimiento en un conjunto diferente de problemas, aumenta la robustez del solucionador. [ 14 ]

Muchos solucionadores utilizan internamente un generador de números aleatorios . Diversificar sus semillas es una forma sencilla de diversificar una cartera. Otras estrategias de diversificación implican habilitar, deshabilitar o diversificar ciertas heurísticas en el solucionador secuencial. [ 15 ]

Una desventaja de las carteras paralelas es la cantidad de trabajo duplicado. Si se utiliza el aprendizaje de cláusulas en los solucionadores secuenciales, compartir las cláusulas aprendidas entre solucionadores que se ejecutan en paralelo puede reducir el trabajo duplicado y aumentar el rendimiento. Sin embargo, incluso simplemente ejecutar una cartera de los mejores solucionadores en paralelo crea un solucionador paralelo competitivo. Un ejemplo de dicho solucionador es PPfolio. [ 16 ] [ 17 ] Fue diseñado para encontrar un límite inferior para el rendimiento que un solucionador SAT paralelo debería poder ofrecer. A pesar de la gran cantidad de trabajo duplicado debido a la falta de optimizaciones, tuvo un buen rendimiento en una máquina de memoria compartida. HordeSat [ 18 ] es un solucionador de cartera paralela para grandes clústeres de nodos de computación. Utiliza instancias configuradas de manera diferente del mismo solucionador secuencial en su núcleo. Particularmente para instancias SAT difíciles, HordeSat puede producir aceleraciones lineales y, por lo tanto, reducir significativamente el tiempo de ejecución.

En los últimos años, los solucionadores SAT de cartera paralela han dominado la pista paralela de las Competiciones Internacionales de Solucionadores SAT. Ejemplos notables de dichos solucionadores incluyen Plingeling y painless-mcomsps. [ 19 ]

Divide y vencerás

A diferencia de las carteras paralelas, el algoritmo de divide y vencerás paralelo intenta dividir el espacio de búsqueda entre los elementos de procesamiento. Los algoritmos de divide y vencerás, como el DPLL secuencial, ya aplican la técnica de división del espacio de búsqueda, por lo que su extensión a un algoritmo paralelo es directa. Sin embargo, debido a técnicas como la propagación de unidades, tras una división, los problemas parciales pueden diferir significativamente en complejidad. Por lo tanto, el algoritmo DPLL normalmente no procesa cada parte del espacio de búsqueda en el mismo tiempo, lo que genera un problema de equilibrio de carga complejo . [ 14 ]

Árbol que ilustra la fase de anticipación y los cubos resultantes.
Fase cúbica para la fórmulaF{\displaystyle F}La heurística de decisión elige qué variables (círculos) asignar. Una vez que la heurística de corte decide detener la ramificación, los problemas parciales (rectángulos) se resuelven de forma independiente utilizando CDCL.

Debido al retroceso no cronológico, la paralelización del aprendizaje de cláusulas basado en conflictos es más difícil. Una forma de superar esto es el paradigma Cube-and-Conquer. [ 20 ] Este propone resolver en dos fases. En la fase de "cubo", el problema se divide en miles, incluso millones, de secciones. Esto se realiza mediante un solucionador con anticipación, que encuentra un conjunto de configuraciones parciales llamadas "cubos". Un cubo también puede verse como una conjunción de un subconjunto de variables de la fórmula original. Junto con la fórmula, cada uno de los cubos forma una nueva fórmula. Estas fórmulas pueden ser resueltas de forma independiente y concurrente por solucionadores basados ​​en conflictos. Como la disyunción de estas fórmulas es equivalente a la fórmula original, se informa que el problema es satisfacible, si una de las fórmulas lo es. El solucionador con anticipación es favorable para problemas pequeños pero difíciles, [ 21 ] por lo que se utiliza para dividir gradualmente el problema en múltiples subproblemas. Estos subproblemas son más fáciles, pero aún así grandes, lo cual es la forma ideal para un solucionador basado en conflictos. Además, los solucionadores de anticipación consideran el problema completo, mientras que los solucionadores basados ​​en conflictos toman decisiones basándose en información mucho más local. Hay tres heurísticas involucradas en la fase del cubo. Las variables en los cubos se eligen mediante la heurística de decisión. La heurística de dirección decide qué asignación de variable (verdadera o falsa) explorar primero. En instancias de problemas satisfacibles, elegir una rama satisfacible primero es beneficioso. La heurística de corte decide cuándo dejar de expandir un cubo y, en su lugar, enviarlo a un solucionador secuencial basado en conflictos. Preferiblemente, los cubos tienen una complejidad similar para resolver. [ 20 ]

Treengeling es un ejemplo de solucionador paralelo que aplica el paradigma Cube-and-Conquer. Desde su introducción en 2012, ha cosechado múltiples éxitos en la International SAT Solver Competition. Cube-and-Conquer se utilizó para resolver el problema de las ternas pitagóricas booleanas . [ 22 ]

Cube-and-Conquer es una modificación o una generalización del enfoque Divide-and-conquer basado en DPLL utilizado para calcular los números de Van der Waerden w(2;3,17) y w(2;3,18) en 2010 [ 23 ] donde ambas fases (división y resolución de los problemas parciales) se realizaron utilizando DPLL.

Una estrategia para un algoritmo de búsqueda local paralelo para la resolución de problemas SAT consiste en probar múltiples cambios de variables simultáneamente en diferentes unidades de procesamiento. [ 24 ] Otra estrategia es aplicar el enfoque de cartera mencionado anteriormente; sin embargo, no es posible compartir cláusulas, ya que los solucionadores de búsqueda local no generan cláusulas. Como alternativa, es posible compartir las configuraciones que se generan localmente. Estas configuraciones pueden utilizarse para guiar la generación de una nueva configuración inicial cuando un solucionador local decide reiniciar su búsqueda. [ 25 ]

Enfoques aleatorios

Entre los algoritmos que no pertenecen a la familia DPLL se incluyen los algoritmos de búsqueda local estocástica . Un ejemplo es WalkSAT . Los métodos estocásticos intentan encontrar una interpretación satisfactoria, pero no pueden deducir que una instancia SAT sea insatisfacible, a diferencia de los algoritmos completos, como DPLL. [ 4 ]

En contraste, los algoritmos aleatorios como el algoritmo PPSZ de Paturi, Pudlak, Saks y Zane establecen las variables en un orden aleatorio según algunas heurísticas, por ejemplo, la resolución de ancho limitado . Si la heurística no puede encontrar la configuración correcta, la variable se asigna aleatoriamente. El algoritmo PPSZ tiene un tiempo de ejecución deO(1.308norte){\displaystyle O(1.308^{n})}para 3-SAT. Este fue el tiempo de ejecución más conocido para este problema hasta 2019, cuando Hansen, Kaplan, Zamir y Zwick publicaron una modificación de ese algoritmo con un tiempo de ejecución deO(1.307norte){\displaystyle O(1.307^{n})}para 3-SAT. Este último es actualmente el algoritmo más rápido conocido para k-SAT en todos los valores de k. En el escenario con muchas asignaciones satisfactorias, el algoritmo aleatorio de Schöning tiene una mejor cota. [ 26 ] [ 27 ] [ 28 ]

Aplicaciones

En matemáticas

Los solucionadores SAT se han utilizado para ayudar a demostrar teoremas matemáticos mediante demostración asistida por computadora . En la teoría de Ramsey , se calcularon varios números de Van der Waerden previamente desconocidos con la ayuda de solucionadores SAT especializados que se ejecutan en FPGA . [ 29 ] [ 30 ] En 2016, Marijn Heule , Oliver Kullmann y Victor Marek resolvieron el problema de las ternas pitagóricas booleanas utilizando un solucionador SAT para demostrar que no hay forma de colorear los enteros hasta 7825 de la manera requerida. [ 31 ] [ 32 ] Heule también calculó valores pequeños de los números de Schur utilizando solucionadores SAT. [ 33 ]

En la verificación de software

Los solucionadores SAT se utilizan en la verificación formal de hardware y software . En la verificación de modelos (en particular, la verificación de modelos acotada), los solucionadores SAT se utilizan para comprobar si un sistema de estados finitos satisface una especificación de su comportamiento previsto. [ 34 ] [ 35 ]

Los solucionadores SAT son el componente central sobre el cual se construyen los solucionadores de satisfacibilidad módulo teorías (SMT), que se utilizan para problemas tales como la planificación de trabajos , la ejecución simbólica , la verificación de modelos de programas , la verificación de programas basada en la lógica de Hoare y otras aplicaciones. [ 36 ] Estas técnicas también están estrechamente relacionadas con la programación de restricciones y la programación lógica .

En la planificación automatizada

Los solucionadores SAT (véase Satplan ) se utilizan para los planes de búsqueda. [ 37 ]

En otras áreas

En la investigación operativa , los solucionadores SAT se han aplicado para resolver problemas de optimización y programación. [ 38 ]

En la teoría de la elección social , los solucionadores SAT se han utilizado para demostrar teoremas de imposibilidad. [ 39 ] Tang y Lin utilizaron solucionadores SAT para demostrar el teorema de Arrow y otros teoremas de imposibilidad clásicos. Geist y Endriss lo utilizaron para encontrar nuevas imposibilidades relacionadas con extensiones de conjuntos. Brandt y Geist utilizaron este enfoque para demostrar una imposibilidad sobre soluciones de torneos a prueba de estrategias . Otros autores utilizaron esta tecnología para demostrar nuevas imposibilidades sobre la paradoja de la no presentación , la monotonicidad a medio camino y las reglas de votación probabilísticas . Brandl, Brandt, Peters y Stricker lo utilizaron para demostrar la imposibilidad de una regla a prueba de estrategias, eficiente y justa para la elección social fraccionaria . [ 40 ]

Véase también

Referencias

  1. ↑ Ohrimenko, Olga; Stuckey, Peter J.; Codish, Michael (2007), "Propagación = Generación perezosa de cláusulas", Principios y práctica de la programación con restricciones – CP 2007 , Lecture Notes in Computer Science, vol.  4741, pp. 544–558 , CiteSeerX 10.1.1.70.5471 , doi : 10.1007/978-3-540-74970-7_39 , ISBN   978-3-540-74969-1Los solucionadores SAT modernos a menudo pueden manejar problemas con millones de restricciones y cientos de miles de variables.
  2. ↑ Davis, M.; Putnam, H. (1960). "Un procedimiento computacional para la teoría de la cuantificación". Journal of the ACM . 7 (3): 201. doi : 10.1145/321033.321034 . S2CID 31888376 . 
  3. ↑ Davis, M. ; Logemann, G.; Loveland, D. (1962). "Un programa informático para la demostración de teoremas" (PDF) . Communications of the ACM . 5 (7): 394– 397. doi : 10.1145/368273.368557 . hdl : 2027/mdp.39015095248095 . S2CID 15866917 . 
  4. 1 2 3 Zhang, Lintao; Malik, Sharad (2002), "La búsqueda de solucionadores eficientes de satisfacibilidad booleana", Verificación asistida por computadora , Lecture Notes in Computer Science, vol. 2404, Springer Berlin Heidelberg, pp. 17–36 , doi : 10.1007/3-540-45657-0_2 , ISBN   978-3-540-43997-4{{citation}}: CS1 mantenimiento: parámetro de trabajo con ISBN ( enlace )
  5. ↑ Vizel, Y.; Weissenbacher, G.; Malik, S. (2015). "Solucionadores de satisfacibilidad booleana y sus aplicaciones en la verificación de modelos". Actas del IEEE . 103 (11): 2021– 2035. doi : 10.1109/JPROC.2015.2455034 . S2CID 10190144 . 
  6. ↑ Möhle, Sibylle; Biere, Armin (2019). «Backing Backtracking». Theory and Applications of Satisfiability Testing – SAT 2019 (PDF) . Lecture Notes in Computer Science. Vol. 11628. pp. 250–266 . doi : 10.1007/978-3-030-24258-9_18 . ISBN   978-3-030-24257-2. S2CID 195755607 . 
  7. ↑ Moskewicz, MW; Madigan, CF; Zhao, Y.; Zhang, L.; Malik, S. (2001). "Chaff: Ingeniería de un solucionador SAT eficiente" (PDF) . Actas de la 38.ª conferencia sobre automatización del diseño (DAC) . pág. 530. doi : 10.1145/378239.379017 . ISBN  1581132972. S2CID 9292941 . 
  8. ↑ Marques-Silva, JP; Sakallah, KA (1999). "GRASP: un algoritmo de búsqueda para la satisfacibilidad proposicional" (PDF) . IEEE Transactions on Computers . 48 (5): 506. Bibcode : 1999ITCmp..48..506M . doi : 10.1109/12.769433 . Archivado del original (PDF) el 4 de noviembre de 2016. Recuperado el 28 de agosto de 2015 .
  9. ↑ "ManySAT: un solucionador SAT paralelo" . Archivado del original el 3 de mayo de 2011.
  10. ↑ "Página web de las competiciones internacionales SAT" . Consultado el 15 de noviembre de 2007 .
  11. ↑ "SAT Competition 2016" . baldur.iti.kit.edu . Consultado el 13 de febrero de 2020 .
  12. ↑ "SAT Competition 2017" . baldur.iti.kit.edu . Consultado el 13 de febrero de 2020 .
  13. ↑ "SAT Competition 2018" . sat2018.forsyte.tuwien.ac.at . Archivado del original el 20 de febrero de 2020. Consultado el 13 de febrero de 2020 .
  14. 1 2 Balyo, Tomáš; Sinz, Carsten (2018), "Satisfacibilidad paralela", Manual de razonamiento de restricciones paralelas , Springer International Publishing, pp. 3–29 , doi : 10.1007/978-3-319-63516-3_1 , ISBN  978-3-319-63515-6{{citation}}: CS1 mantenimiento: parámetro de trabajo con ISBN ( enlace )
  15. ^ Biere, Armin. "Lingeling, Plingeling, PicoSAT y PrecoSAT en SAT Race 2010" (PDF) . SAT-RACE 2010 .
  16. ↑ "ppfolio solver" . www.cril.univ-artois.fr . Consultado el 29 de diciembre de 2019 .
  17. ↑ "SAT 2011 Competition: 32 cores track: ranking of solucioners" . www.cril.univ-artois.fr . Consultado el 13 de febrero de 2020 .
  18. ↑ Balyo, Tomáš; Sanders, Peter; Sinz, Carsten (2015), "HordeSat: Un solucionador SAT de cartera masivamente paralelo", Teoría y aplicaciones de las pruebas de satisfacibilidad -- SAT 2015 , Lecture Notes in Computer Science, vol. 9340, Springer International Publishing, pp. 156–172 , arXiv : 1505.03340 , doi : 10.1007/978-3-319-24318-4_12 , ISBN   978-3-319-24317-7, S2CID 11507540 
  19. ↑ "SAT Competition 2018" . sat2018.forsyte.tuwien.ac.at . Archivado del original el 19 de febrero de 2020. Consultado el 13 de febrero de 2020 .
  20. 1 2 Heule, Marijn JH ; Kullmann, Oliver; Wieringa, Siert; Biere, Armin (2012), "Cube and Conquer: Guiding CDCL SAT Solvers by Lookaheads", Hardware and Software: Verification and Testing , Lecture Notes in Computer Science, vol. 7261, Springer Berlin Heidelberg, pp. 50– 65, doi : 10.1007/978-3-642-34188-5_8 , ISBN   978-3-642-34187-8{{citation}}: CS1 mantenimiento: parámetro de trabajo con ISBN ( enlace )
  21. ^ Heule, Marijn JH ; van Maaren, Hans (2009). "Solucionadores SAT basados ​​​​en anticipación" (PDF) . Manual de Satisfacibilidad . Prensa IOS. págs. 155-184 . ISBN  978-1-58603-929-5.
  22. ↑ Heule, Marijn JH ; Kullmann, Oliver; Marek, Victor W. (2016), "Resolución y verificación del problema de las ternas pitagóricas booleanas mediante el método Cube-and-Conquer", Theory and Applications of Satisfiability Testing – SAT 2016 , Lecture Notes in Computer Science, vol. 9710, Springer International Publishing, pp. 228–245 , arXiv : 1605.00723 , doi : 10.1007/978-3-319-40970-2_15 , ISBN   978-3-319-40969-6, S2CID 7912943 {{citation}}: CS1 mantenimiento: parámetro de trabajo con ISBN ( enlace )
  23. ↑ Ahmed, Tanbir (2010). "Dos nuevos números de van der Waerden w(2;3,17) y w(2;3,18)". Enteros . 10 ( 4): 369– 377. doi : 10.1515/integ.2010.032 . MR 2684128. S2CID 124272560 .  
  24. ↑ Roli, Andrea (2002), "Criticidad y paralelismo en instancias SAT estructuradas", Principios y práctica de la programación con restricciones - CP 2002 , Lecture Notes in Computer Science, vol. 2470, Springer Berlin Heidelberg, pp. 714–719 , doi : 10.1007/3-540-46135-3_51 , ISBN   978-3-540-44120-5
  25. ↑ Arbelaez, Alejandro; Hamadi, Youssef (2011), "Improving Parallel Local Search for SAT", Learning and Intelligent Optimization , Lecture Notes in Computer Science, vol. 6683, Springer Berlin Heidelberg, pp. 46–60 , doi : 10.1007/978-3-642-25566-3_4 , ISBN   978-3-642-25565-6, S2CID 14735849 
  26. ↑ Schöning, Uwe (octubre de 1999). «Un algoritmo probabilístico para problemas k-SAT y de satisfacción de restricciones» (PDF) . 40.º Simposio Anual sobre Fundamentos de la Informática (Cat. n.º 99CB37039) . págs. 410-414 . doi : 10.1109/SFFCS.1999.814612 . ISBN  0-7695-0409-4. S2CID 123177576 . 
  27. ↑ "Un algoritmo mejorado de tiempo exponencial para k-SAT" , Paturi, Pudlak, Saks, Zani
  28. ↑ "Algoritmos k-SAT más rápidos usando PPSZ sesgado" , Hansen, Kaplan, Zamir, Zwick
  29. ^ Kouril, Michal; Paul, Jerome L. (2008). "El número de van der Waerden $W(2,6)$ es 1132" . Matemáticas Experimentales . 17 (1): 53– 61. doi : 10.1080/10586458.2008.10129025 . ISSN 1058-6458 . S2CID 1696473 .  
  30. ^ Kouril, Michal (2012). "Calcular el número de van der Waerden W (3,4) = 293". Enteros . 12 : A46. SEÑOR 3083419 . 
  31. ↑ Heule, Marijn JH; Kullmann, Oliver; Marek, Victor W. (2016), "Resolución y verificación del problema de las ternas pitagóricas booleanas mediante el método Cube-and-Conquer", Theory and Applications of Satisfiability Testing – SAT 2016 , Lecture Notes in Computer Science, vol. 9710, pp. 228–245 , arXiv : 1605.00723 , doi : 10.1007/978-3-319-40970-2_15 , ISBN   978-3-319-40969-6, S2CID 7912943 
  32. ↑ Lamb, Evelyn (1 de junio de 2016). "La prueba matemática de doscientos terabytes es la más grande jamás realizada" . Nature . 534 ( 7605): 17–18 . Bibcode : 2016Natur.534...17L . doi : 10.1038/nature.2016.19990 . ISSN 1476-4687 . PMID 27251254. S2CID 5528978 .   
  33. ↑ "Schur Número Cinco" . www.cs.utexas.edu . Consultado el 26 de octubre de 2023 .
  34. ↑ Clarke, Edmund; Biere, Armin; Raimi, Richard; Zhu, Yunshan (2001-07-01). "Verificación de modelos acotada mediante resolución de satisfacibilidad" . Métodos formales en diseño de sistemas . 19 (1): 7– 34. doi : 10.1023/A:1011276507260 . ISSN 1572-8102 . S2CID 2484208 .  
  35. ↑ Biere, Armin; Cimatti, Alessandro; Clarke, Edmund M.; Strichman, Ofer; Zhu, Yunshan (2003). "Bounded Model Checking" (PDF) . Advances in Computers . 58 (2003): 117–148 . doi : 10.1016/S0065-2458(03)58003-2 . ISBN 9780120121588– vía Academic Press.
  36. ↑ De Moura, Leonardo; Bjørner, Nikolaj (2011-09-01). "Satisfacibilidad módulo teorías: introducción y aplicaciones" . Communications of the ACM . 54 (9): 69– 77. doi : 10.1145/1995376.1995394 . ISSN 0001-0782 . S2CID 11621980 .  
  37. ↑ Kautz, Henry; Selman, Bart (agosto de 1992). "Planning as Satisfiability" . CiteSeerX . ECAI'92. Archivado del original el 25 de enero de 2019.
  38. ↑ Coelho, José; Vanhoucke, Mario (16 de agosto de 2011). "Programación de proyectos con restricciones de recursos en múltiples modos utilizando solucionadores RCPSP y SAT" . European Journal of Operational Research . 213 (1): 73–82 . doi : 10.1016/j.ejor.2011.03.019 . ISSN 0377-2217 . 
  39. ↑ Peters, Dominik (2021). "Proporcionalidad y resistencia a la estrategia en elecciones multiganadoras". arXiv : 2104.08594 [ cs.GT ].
  40. ↑ Brandl, Florian; Brandt, Felix; Peters, Dominik; Stricker, Christian (18 de julio de 2021). «Reglas de distribución bajo preferencias dicotómicas: dos de tres no está mal» . Actas de la 22.ª Conferencia ACM sobre Economía y Computación . EC '21. Nueva York, NY, EE. UU.: Association for Computing Machinery. págs. 158–179 . doi : 10.1145/3465456.3467653 . ISBN  978-1-4503-8554-1. S2CID 232109303 . 
  • Resumen de las competiciones SAT desde 2002