logo móvil
Contáctanos

Resolvable networks: una herramienta gráfica para representar y resolver SAT

Autores: Kusper, Gábor; Biró, Csaba; Nagy, Benedek

Idioma: Inglés

Editor: MDPI

Año: 2021

Descargar PDF

Acceso abierto

Artículo científico
2021

Resolvable networks: una herramienta gráfica para representar y resolver SAT


Categoría

Matemáticas

Subcategoría

Matemáticas generales

Palabras clave

Redes resolubles
Subredes
Problema SAT
Resolución
Interpretación pesimista
Interpretación optimista

Licencia

CC BY-SA – Atribución – Compartir Igual

Consultas: 29

Citaciones: Sin citaciones


Descripción
En este documento, presentamos el concepto de redes resolubles. Una red resoluble es un digrafo de subredes, donde las subredes pueden superponerse, y la estructura interna de las subredes no es interesante desde el punto de vista de la red. Hay dos subredes especiales, Origen y Sumidero, con las siguientes propiedades: no hay arista entrante hacia el Origen, y no hay arista saliente desde el Sumidero. Cualquier red resoluble puede ser representada por un problema de satisfacibilidad en lógica booleana (abreviado, problema SAT), y cualquier problema SAT puede ser representado por una red resoluble. Debido a eso, la operación de resolución es válida también para redes resolubles. Podemos usar la resolución para descubrir o refinar la estructura interna de las subredes. También damos una interpretación pesimista y una optimista de las subredes. En el caso pesimista, asumimos que dentro de una subred, todas las posibilidades de comunicación están representadas como parte de la red resoluble. En el caso optimista, asumimos que cada subred está fuertemente conectada. Mostramos que cualquier problema SAT puede ser visualizado utilizando la interpretación pesimista. Mostramos que la transitividad es muy limitada en la interpretación pesimista, y en este caso, la transitividad corresponde a la resolución de cláusulas. En la interpretación optimista de las subredes, tenemos transitividad sin ninguna otra condición, pero no todos los problemas SAT pueden ser representados en este caso; sin embargo, cualquier red de este tipo puede ser representada como un problema SAT. El concepto gráfico recién introducido permite utilizar terminología y herramientas de grafos dirigidos en el campo de SAT y también dar representaciones gráficas de varios conceptos de problemas de satisfacibilidad. Una red resoluble también es una estructura de datos adecuada para estudiar, por ejemplo, redes de sensores inalámbricos. El poder de visualización de las redes resolubles se demuestra en algunos problemas SAT de agujeros de paloma. Otro campo de aplicación importante podría ser modelar la red de comunicación de un banco de información. Aquí, una subred representa un conjunto de datos de un usuario que está asegurado por un proxy. Cualquier comunicación debe realizarse a través del proxy, y esta restricción se puede verificar utilizando nuestro modelo.

Otros recursos que podrían interesarte

Temas Virtualpro