Please use this identifier to cite or link to this item:
https://rinacional.tecnm.mx/jspui/handle/TecNM/3220| Title: | Revisión de la Aplicación de Transformaciones Entre Problemas en la Teoría de la Completitud-NP |
| Authors: | Ong de la Cruz, Ernesto A. |
| Issue Date: | 2012-02-01 |
| Publisher: | Tecnológico Nacional de México |
| metadata.dc.publisher.tecnm: | Instituto Tecnológico de Ciudad Madero |
| Description: | Este proyecto de tesis fue originado por la tesis doctoral de Jorge Alberto Ruiz Vanoye en la que se buscó proponer una transformación polinomial entre el problema de Bin-Packing a 2-Partition. Partiendo del conocimiento de que existía una transformación polinomial de 2-Partition a Bin-Packing, se pretendió realizar la transformación en sentido contrario, basándose en la definición de completitud-NP, según la cual debería de existir la transformación de Bin-Packing a 2-Partition. Sin embargo, los resultados no fueron del todo satisfactorios, ya que no se pudieron transformar correctamente todos los ejemplares de prueba. Para comprender por qué fue imposible encontrar una transformación satisfactoria, se revisó la teoría de la completitud-NP y la definición de transformación polinomial. El resultado de dicha revisión fue el establecimiento de tres condiciones implícitas que debe cumplir cualquier transformación entre problemas NP-completos. Al aplicar estas condiciones a la transformación 2-Partition a Bin-Packing, se encontró que no cumplía con una de las condiciones implícitas; por lo tanto, se decidió revisar bajo las mismas condiciones a la rama de transformaciones que van desde el problema de Bin Packing hasta el problema de Satisfactibilidad (SAT) con el fin de verificar que cumplan dichas condiciones. Todo parece indicar que no hay ningún error en las transformaciones hasta ahora revisadas, pero se ha encontrado que para algunas de ellas no ha sido posible encontrar una transformación revertida o transformación en sentido contrario. En la mayor parte de las demostraciones de completitud-NP de un problema sólo se incluye la transformación en un solo sentido, omitiendo la de sentido inverso, lo cual da a sospechar que tal vez dicha transformación no es posible o es muy difícil de diseñar. Uno de los propósitos de la completitud-NP es establecer una relación entre los problemas NP-completos mediante la cual, si tal sólo se encuentra un algoritmo que resuelva polinomialmente cualquier problema NP-completo, entonces todos los problemas NP-completos también serán resueltos. El método para establecer esta relación entre dos problemas NP-completos es la transformación polinomial, y para cumplir con el propósito antes mencionado, es lógico pensar que debe poder transformarse en ambos sentidos. Dado que el término de transformación inversa no está bien definido y que el término transformación está relacionada al de función, podría suponerse que el término de transformación inversa es idéntico al de función inversa. Por lo tanto, se propone el término de transformación revertida a una transformación polinomial entre dos problemas 1 y 2 NP-completos que va de 2 a 1 cuando ya existe una transformación polinomial de 1 a 2 |
| metadata.dc.type: | info:eu-repo/semantics/masterThesis |
| Appears in Collections: | Maestría en Ciencias de la Computación |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| G04070511_donacion_tesis_bib.pdf | 2.86 MB | Adobe PDF | View/Open |
This item is protected by original copyright |
This item is licensed under a Creative Commons License
