Instancias SAT aleatorias sin escala
Autores: Ansótegui, Carlos; Bonet, Maria Luisa; Levy, Jordi
Idioma: Inglés
Editor: MDPI
Año: 2022
Acceso abierto
Artículo científico
2022
Instancias SAT aleatorias sin escala
Categoría
Ingeniería y Tecnología
Subcategoría
Ingeniería de Software
Palabras clave
Generación aleatoria
Instancias de SAT
Instancias industriales
Solucionador
Distribución de probabilidad no uniforme
Distribución de ley de potencia
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 33
Citaciones: Sin citaciones
Nos enfocamos en la generación aleatoria de instancias de SAT que tienen propiedades similares a las instancias del mundo real. Se sabe que muchas instancias industriales, incluso con un gran número de variables, pueden ser resueltas por un solucionador inteligente en un tiempo razonable. Esto no es posible, en general, con instancias generadas aleatoriamente de manera clásica. Proporcionamos un modelo de generación diferente de instancias de SAT, llamado "This", basado en el uso de una distribución de probabilidad no uniforme para seleccionar variables , donde es un parámetro del modelo. Esto resulta en fórmulas donde el número de ocurrencias de variables sigue una distribución de ley de potencias , donde . Esta propiedad ha sido observada en la mayoría de las instancias reales de SAT. Para , nuestro modelo extiende las instancias clásicas de SAT aleatorias. Demostramos la existencia de un fenómeno de transición de fase SAT-UNSAT para instancias de 2-SAT aleatorias de ley de potencias con cuando la relación cláusula/variable es . También demostramos que las instancias de k-SAT aleatorias de ley de potencias son insatisfacibles con una alta probabilidad cuando el número de cláusulas excede . La prueba de este resultado sugiere que, cuando , la insatisfacibilidad de la mayoría de las fórmulas puede deberse a núcleos pequeños de cláusulas. Finalmente, mostramos cómo este modelo nos permitirá generar instancias aleatorias similares a instancias industriales, de interés para propósitos de prueba.
Descripción
Nos enfocamos en la generación aleatoria de instancias de SAT que tienen propiedades similares a las instancias del mundo real. Se sabe que muchas instancias industriales, incluso con un gran número de variables, pueden ser resueltas por un solucionador inteligente en un tiempo razonable. Esto no es posible, en general, con instancias generadas aleatoriamente de manera clásica. Proporcionamos un modelo de generación diferente de instancias de SAT, llamado "This", basado en el uso de una distribución de probabilidad no uniforme para seleccionar variables , donde es un parámetro del modelo. Esto resulta en fórmulas donde el número de ocurrencias de variables sigue una distribución de ley de potencias , donde . Esta propiedad ha sido observada en la mayoría de las instancias reales de SAT. Para , nuestro modelo extiende las instancias clásicas de SAT aleatorias. Demostramos la existencia de un fenómeno de transición de fase SAT-UNSAT para instancias de 2-SAT aleatorias de ley de potencias con cuando la relación cláusula/variable es . También demostramos que las instancias de k-SAT aleatorias de ley de potencias son insatisfacibles con una alta probabilidad cuando el número de cláusulas excede . La prueba de este resultado sugiere que, cuando , la insatisfacibilidad de la mayoría de las fórmulas puede deberse a núcleos pequeños de cláusulas. Finalmente, mostramos cómo este modelo nos permitirá generar instancias aleatorias similares a instancias industriales, de interés para propósitos de prueba.