Un estudio experimental de los efectos de resolución extendida para los solucionadores SAT en el principio de las casillas del palomar
Autores: Sonobe, Tomohiro
Idioma: Inglés
Editor: MDPI
Año: 2022
Acceso abierto
Artículo científico
2022
Un estudio experimental de los efectos de resolución extendida para los solucionadores SAT en el principio de las casillas del palomar
Categoría
Ingeniería y Tecnología
Subcategoría
Ingeniería de Software
Palabras clave
Probado
Resolución extendida
Principio del cajón de palomas
Paper de Cook
Solucionadores de SAT
Variables auxiliares
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 30
Citaciones: Sin citaciones
Se ha demostrado que la resolución extendida (ER) tiene un razonamiento más potente que la resolución general para el principio de los agujeros de paloma en el documento de Cook. Este hecho indica la posibilidad de que un solucionador basado en la resolución extendida pueda superar a los solucionadores de problemas de satisfacción booleana (SAT, por sus siglas en inglés) basados en la resolución general. Sin embargo, pocos estudios han proporcionado evidencia práctica de esta suposición. Este documento explora cómo la resolución extendida puede mejorar los solucionadores SAT utilizando el principio de los agujeros de paloma, que fue el primer problema resuelto por ER en pasos polinómicos. De hecho, aunque el documento de Cook introdujo cómo agregar variables auxiliares, no hay evidencia de que estas variables sean realmente útiles para los solucionadores prácticos. Intentamos responder a la pregunta: Si el solucionador SAT puede agregar variables auxiliares apropiadas como se propone en el documento de Cook, ¿puede el solucionador mejorar su rendimiento utilizando estas variables? Los resultados experimentales muestran que si el solucionador prioriza adecuadamente las variables extendidas en la búsqueda, el solucionador puede finalizar la búsqueda en menos tiempo.
Descripción
Se ha demostrado que la resolución extendida (ER) tiene un razonamiento más potente que la resolución general para el principio de los agujeros de paloma en el documento de Cook. Este hecho indica la posibilidad de que un solucionador basado en la resolución extendida pueda superar a los solucionadores de problemas de satisfacción booleana (SAT, por sus siglas en inglés) basados en la resolución general. Sin embargo, pocos estudios han proporcionado evidencia práctica de esta suposición. Este documento explora cómo la resolución extendida puede mejorar los solucionadores SAT utilizando el principio de los agujeros de paloma, que fue el primer problema resuelto por ER en pasos polinómicos. De hecho, aunque el documento de Cook introdujo cómo agregar variables auxiliares, no hay evidencia de que estas variables sean realmente útiles para los solucionadores prácticos. Intentamos responder a la pregunta: Si el solucionador SAT puede agregar variables auxiliares apropiadas como se propone en el documento de Cook, ¿puede el solucionador mejorar su rendimiento utilizando estas variables? Los resultados experimentales muestran que si el solucionador prioriza adecuadamente las variables extendidas en la búsqueda, el solucionador puede finalizar la búsqueda en menos tiempo.