About the work
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.
El presente material interactivo pretende facilitar 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.
Copyright registered declarations
Universidad de Málaga
Derechos de explotación incluyendo comunicación, distribución, reproducción y transformación.
Todo el mundo
Scope: Todos los ámbitos de explotación
Consolidated inscription:
Copyright infringement notifications:
0
Contact
Consolidated inscription:
Copyright infringement notifications:
0
Contact
Consolidated inscription:
Copyright infringement notifications:
0
Contact
Consolidated inscription:
Copyright infringement notifications:
0
Contact
Notify irregularities in this registration
AI Availability Declaration
AI systems will only be able to access the work with prior agreement
Creativity declaration
No AI has been used in the creative process of this work
Print work information
Work information
Title Herramienta para la visualización de reducciones entre el problema SAT y otros problemas NPC
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.
El presente material interactivo pretende facilitar 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.
Work type Software and Database designs
Tags complejidad computacional, np-completitud, sat problem, np-completeness, representación visual, reducibility between problems, problema sat, reducibilidad entre problemas, visual representation, computational complexity
-------------------------
Registry info in Safe Creative
Identifier 2511053594425
Entry date Nov 5, 2025, 12:13 PM UTC
License GNU General Public License 3.0
-------------------------
Copyright registered declarations
Derechos de explotación incluyendo comunicación, distribución, reproducción y transformación. 100.00 %. Holder Universidad de Málaga. Date Nov 5, 2025. Geographic coverage: Todo el mundo. Scope Todos los ámbitos de explotación.
Author 50.00 %. Holder Paula Guzmán. Date Nov 5, 2025.
Author 25.00 %. Holder José del Campo-Ávila. Date Nov 8, 2025.
Author 25.00 %. Holder Rafael Morales. Date Dec 6, 2025.
Information available at https://www.safecreative.org/work/2511053594425-herramienta-para-la-visualizacion-de-reducciones-entre-el-problema-sat-y-otros-problemas-npc
/
Registration: 2511053594425
