RT Generic
T1 Herramienta para la visualización de reducciones entre el problema SAT y otros problemas NPC
T2 Tool for visualization of reductions between the SAT problem and other NPC problems
A1 Guzmán Enríquez, Paula del Carmen
K1 Informática - Trabajos Fin de Grado
K1 Grado en Ingeniería Informática - Trabajos Fin de Grado
AB El problema de la satisfacibilidad boolena (SAT) fue el primer problema identificado comoperteneciente a la clase de complejidad NP-completo. Este problema, aunque no inicialmenteligado a la informática, guarda una estrecha relación con ella gracias a la teoría de la complejidadcomputacional.Se tiene como propósito crear un material interactivo que facilite la comprensión de las reducibilidadesentre problemas NP-completos. Se consigue mediante la demostración de cómo apartir de SAT, es posible reducir polinómicamente otros problemas NP-completos relacionadoscon la informática. Para ello, se desarrolla una aplicación web que describe el proceso dedichas reducciones. Este contempla tres etapas principales:1. Transformación de una fórmula booleana dada por el usuario a una 3FNC (forma normalconjuntiva de 3 literales por cláusula). Se usan mapas de Karnaugh para una simplificaciónmás eficiente de la fórmula.2. Reducción del problema 3SAT (que expresa fórmulas booleanas 3FNC) a otro problemaNP-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 posibilidadal usuario de elegir una solución a mostrar entre todas las posibles. La solución elegidase representa visualmente.Las reducciones se detallan para 4 problemas NP-completos: CLIQUE, VERTEX-COVER, HAMPATHy SUBSET-SUM.Asimismo, cada uno de los problemas se complementa con una explicación detallada de lasreducciones realizadas, con el fin de facilitar la comprensión por parte del usuario.
YR 2025
FD 2025
LK https://hdl.handle.net/10630/45975
UL https://hdl.handle.net/10630/45975
LA spa
DS RIUMA. Repositorio Institucional de la Universidad de Málaga
RD 18 mar 2026