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 1: | Línea 1: | ||
==Ejercicio 11.01:== | ==Ejercicio 11.01:== | ||
<br>a) Se puede hacer en O(n log n) -> esta en P | <br>a) Se puede hacer en O(n log n) -> esta en P | ||
Línea 25: | Línea 8: | ||
==Ejercicio 11.03:== | ==Ejercicio 11.03:== | ||
==Ejercicio 11.04:== | ==Ejercicio 11.04:== | ||
==Ejercicio 11.05:== | ==Ejercicio 11.05:== | ||
<br>a) | <br>a) | ||
Línea 38: | Línea 14: | ||
<br>c) | <br>c) | ||
==Ejercicio 11.06:== | ==Ejercicio 11.06:== | ||
==Ejercicio 11.07:== | ==Ejercicio 11.07:== | ||
<br>a)Verdadera | <br>a)Verdadera | ||
<br>b)Verdadera | <br>b)Verdadera | ||
<br>c) | <br>c)No se sabe | ||
<br>d)Falso | <br>d)Falso | ||
<br>e) | <br>e) | ||
<br>f) | <br>f) | ||
<br>g)Falso | <br>g)Falso | ||
Posted By Alejandro | |||
==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:== | ||
<br>a)Falso | <br>a)Falso | ||
<br>b)Si el problema de decision Y esta en P y X <=p Y, entonces el | <br>b) Si el problema de decision Y esta en P y X <=p Y, entonces el | ||
problema de decision X esta en P. | problema de decision X esta en P. | ||
<br> | <br> Demostracion: | ||
<br> Sea p el polinomio que acota la complejidad en tiempo del algoritmo de transformacion, y q el polinomio que acota la complejidad del algoritmo polinomico | |||
para B. | |||
<br> Supongamos que tenemos una instancia para A de tamaño n. | |||
<br> Como el algoritmo de transformacion da como mucho p(n) pasos, el tamaño de | |||
la instancia del problema B es como mucho p(n). | |||
<br> El algoritmo para B realiza como mucho q(p(n)) pasos. | |||
<br> Por tanto, la cantidad total de trabajo para resolver A es como mucho p(n) + | |||
q(p(n)), que es un polinomio en n. | |||
<br> | |||
<br>c) | |||
<br>d) | |||
<br>e) | <br>e) | ||
<br>f)Verdadero | <br>f)Verdadero | ||
<br>Un problema C es NP-completo si | <br>Un problema C es NP-completo si | ||
<br>1. esta en NP, y | <br>1. esta en NP, y | ||
<br>2. para algun problema NP-completo B, B <=p C. | <br>2. para algun problema NP-completo B, B <=p C. | ||
<br>Demostracion: | <br>Demostracion: | ||
<br> Por ser B NP-completo, para cualquier problema A en NP, A <=p B. | <br> Por ser B NP-completo, para cualquier problema A en NP, A <=p B. | ||
Línea 94: | Línea 93: | ||
<br>g)Falso | <br>g)Falso | ||
<br> (Hint: Ver 11.8) | <br> (Hint: Ver 11.8) | ||
<br> Los dos problemas pueden ser NP-Completos, ya que por reducibilidad la caracteristica de un problema NP-Completo es que se puede reducir a cualquier otro problema NP. Con lo cual, un problema NP-Completo se puede reducir a otro Problema NP-Completo (Ej: SAT, es la semilla para ir encontrando problemas NP-completos | <br> Los dos problemas pueden ser NP-Completos, ya que por reducibilidad la caracteristica de un problema NP-Completo es que se puede reducir a cualquier otro problema NP. | ||
<br>Con lo cual, un problema NP-Completo se puede reducir a otro Problema NP-Completo(Ej:SAT, es la semilla para ir encontrando problemas NP-completos ) | |||
Línea 116: | Línea 103: | ||
Posted By Alejandro | Posted By Alejandro | ||
==Ejercicio 11.10:== | |||
<br>a) | |||
<br>b) | |||
<br>c) | |||
==Ejercicio 11.11:== | ==Ejercicio 11.11:== | ||
<br>a) | <br>a) | ||
<br>b) | <br>b) | ||
<br>c) | <br>c) | ||
<br>d) | <br>d) | ||
<br>e) | <br>e) | ||
<br>f) | <br>f) | ||
==Ejercicio 11.12:== | ==Ejercicio 11.12:== | ||
==Ejercicio 11.13:== | ==Ejercicio 11.13:== | ||
<br>a) | <br>a) | ||
<br>b) | <br>b) | ||
<br>c) | <br>c) | ||
==Ejercicio 11.14:== | ==Ejercicio 11.14:== | ||
<br>a) | <br>a) | ||
<br>b) | <br>b) | ||
<br>c) | <br>c) | ||
==Ejercicio 11.15:== | ==Ejercicio 11.15:== | ||
==Ejercicio 11.16:== | ==Ejercicio 11.16:== | ||
==Ejercicio 11.17:== | ==Ejercicio 11.17:== | ||
<br>a) | |||
<br>a) | <br>b) | ||
<br>b) | |||
==Ejercicio 11.18:== | ==Ejercicio 11.18:== | ||
==Ejercicio 11.19:== | ==Ejercicio 11.19:== | ||
==Ejercicio 11.20:== | ==Ejercicio 11.20:== | ||
==Ejercicio 11.21:== | ==Ejercicio 11.21:== | ||
Línea 231: | Línea 153: | ||
Si pudieramos mostrar que un problema NP-completo cualquiera | Si pudieramos mostrar que un problema NP-completo cualquiera | ||
está en P, podríamos concluir que P = NP. | está en P, podríamos concluir que P = NP. | ||
<br>b) | <br>b) | ||
Línea 241: | Línea 161: | ||
<br> Aunque, si este fuera NP-Completo tambien demostraria que todos los NP-Completos no tienen solucion polinomica. | <br> Aunque, si este fuera NP-Completo tambien demostraria que todos los NP-Completos no tienen solucion polinomica. | ||
Línea 249: | Línea 170: | ||
Posted By Alejandro | Posted By Alejandro | ||
==Ejercicio 11.23:== | ==Ejercicio 11.23:== | ||
<br>a) | <br>a) | ||
<br>b) | <br>b) | ||