logo móvil
Contáctanos

Codificación fraccional de restricciones de a lo sumo K en SAT

Autores: Yonekura, Miki; Nishimura, Shunji

Idioma: Inglés

Editor: MDPI

Año: 2023

Descargar PDF

Acceso abierto

Artículo científico
2023

Codificación fraccional de restricciones de a lo sumo K en SAT


Categoría

Ingeniería y Tecnología

Subcategoría

Ingeniería Eléctrica y Electrónica

Palabras clave

Problema de satisfactibilidad
Lógica proposicional
Solucionadores SAT
Codificación SAT
Codificación Fraccional
Complejidad computacional

Licencia

CC BY-SA – Atribución – Compartir Igual

Consultas: 42

Citaciones: Sin citaciones


Descripción
El problema de satisfacibilidad (SAT) en lógica proposicional determina si hay una asignación de valores que haga que una fórmula proposicional dada sea verdadera. Recientemente, se han desarrollado solucionadores SAT rápidos, y la investigación de codificación SAT ha ganado atención. Esto permite que varios problemas del mundo real se transformen en SAT y se resuelvan, logrando una solución a los problemas originales. Proponemos un nuevo método de codificación, Codificación Fraccional, que se centra en las restricciones de "A lo más K" -un cuello de botella de complejidad computacional- y reduce la escala de las expresiones lógicas dividiendo las variables objetivo. Además, confirmamos que la Codificación Fraccional supera a los métodos existentes en términos del número de cláusulas generadas y variables auxiliares requeridas. Por lo tanto, permite la resolución eficiente de problemas del mundo real como la planificación y la verificación de hardware.

Otros recursos que podrían interesarte

Temas Virtualpro