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
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
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.
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.