logo móvil
Contáctanos

Instancias SAT aleatorias sin escala

Autores: Ansótegui, Carlos; Bonet, Maria Luisa; Levy, Jordi

Idioma: Inglés

Editor: MDPI

Año: 2022

Descargar PDF

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


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.

Otros recursos que podrían interesarte

Temas Virtualpro