logo móvil
Contáctanos

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

Descargar PDF

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


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.

Otros recursos que podrían interesarte

Temas Virtualpro