2026-06-05T12:44:29Zhttps://riuma.uma.es/rest/oai/requestoai:riuma.uma.es:10630/459752026-03-11T00:47:16Zcom_10630_1685col_10630_38055
00925njm 22002777a 4500
dc
Guzmán Enríquez, Paula del Carmen
author
2025
El problema de la satisfacibilidad boolena (SAT) fue el primer problema identificado como
perteneciente a la clase de complejidad NP-completo. Este problema, aunque no inicialmente
ligado a la informática, guarda una estrecha relación con ella gracias a la teoría de la complejidad
computacional.
Se tiene como propósito crear un material interactivo que facilite la comprensión de las reducibilidades
entre problemas NP-completos. Se consigue mediante la demostración de cómo a
partir de SAT, es posible reducir polinómicamente otros problemas NP-completos relacionados
con la informática. Para ello, se desarrolla una aplicación web que describe el proceso de
dichas reducciones. Este contempla tres etapas principales:
1. Transformación de una fórmula booleana dada por el usuario a una 3FNC (forma normal
conjuntiva de 3 literales por cláusula). Se usan mapas de Karnaugh para una simplificación
más eficiente de la fórmula.
2. Reducción del problema 3SAT (que expresa fórmulas booleanas 3FNC) a otro problema
NP-completo que dispone de una representación visual (como CLIQUE o HAMPATH).
3. Identificación de posibles soluciones para cada problema individual. Se da la posibilidad
al usuario de elegir una solución a mostrar entre todas las posibles. La solución elegida
se representa visualmente.
Las reducciones se detallan para 4 problemas NP-completos: CLIQUE, VERTEX-COVER, HAMPATH
y SUBSET-SUM.
Asimismo, cada uno de los problemas se complementa con una explicación detallada de las
reducciones realizadas, con el fin de facilitar la comprensión por parte del usuario.
https://hdl.handle.net/10630/45975
Informática - Trabajos Fin de Grado
Grado en Ingeniería Informática - Trabajos Fin de Grado
Herramienta para la visualización de reducciones entre el problema SAT y otros problemas NPC