Edición de «Práctica 11: Problemas P y NP (Algoritmos III)»
De Cuba-Wiki
Puedes deshacer la edición. Antes de deshacer la edición, comprueba la siguiente comparación para verificar que realmente es lo que quieres hacer, y entonces publica los cambios para así efectuar la reversión.
Revisión actual | Tu texto | ||
Línea 54: | Línea 54: | ||
==Ejercicio 11.08:== | ==Ejercicio 11.08:== | ||
<br>ES cierto. Justamente la relacion de reducibilidad dice: Si existe un algoritmo de transformacion polinomico del problema de decision A en el problema de decision B, el problema A es reducible polinomicamente al problema B. Lo denotamos: A <=p B. | <br>ES cierto. | ||
<br>Justamente la relacion de reducibilidad dice: Si existe un algoritmo de transformacion polinomico del problema de decision A en el problema de decision B, el problema A es reducible polinomicamente al problema B. Lo denotamos: | |||
<br> A <=p B. | |||
<br>Ademas sabemos que un problema B es NP-completo si: | <br>Ademas sabemos que un problema B es NP-completo si: | ||
<br> | |||
<br>1. esta en NP, y | <br>1. esta en NP, y | ||
<br>2. para cualquier otro problema A en NP, A <=p B. | <br>2. para cualquier otro problema A en NP, A <=p B. | ||
<br>Ya que existe una transformacion polinomica para reducir el algoritmo X a Y, de igual forma Y a X. | <br>Ya que existe una transformacion polinomica para reducir el algoritmo X a Y, de igual forma Y a X. | ||
<br>Con lo cual , llamemos A=X, B=Y, entonces se cumple que X <=p Y, luego | |||
<br>Sea A=Y,B=X, entonces se cumple que X <=p Y. | <br> Con lo cual , llamemos A=X, B=Y, entonces se cumple que X <=p Y, luego | ||
<br> Sea A=Y,B=X, entonces se cumple que X <=p Y. | |||
<br>Fin | <br>Fin | ||
Posted By Alejandro | |||
==Ejercicio 11.09:== | ==Ejercicio 11.09:== |