Herramienta para la visualización de reducciones entre el problema SAT y otros problemas NPC

Abstract

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.