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: | ||
==Propiedades== | ==Propiedades== | ||
(Para todo π: Problema) | (Para todo π: Problema) | ||
Línea 13: | Línea 11: | ||
** 2. π є '''NP-Hard''',es decir, (<math>\forall</math> π' є NP) π' <=p π | ** 2. π є '''NP-Hard''',es decir, (<math>\forall</math> π' є NP) π' <=p π | ||
* (TEO) P <math>\subseteq</math> NP y P <math>\subseteq</math> co-NP | * (TEO) P <math>\subseteq</math> NP y P <math>\subseteq</math> co-NP | ||
* (TEO) Si P <math>\cap</math> NP-Completo <math>\neq \empty</math>, o NP-P | * (TEO) Si P <math>\cap</math> NP-Completo <math>\neq \empty</math>, o NP-P <math>\neq \empty</math> -> P=NP | ||
* (TEO) (Cook) SAT es NP-Completo | * (TEO) (Cook) SAT es NP-Completo | ||
Línea 25: | Línea 23: | ||
==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 29: | ||
<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:== | ||
Línea 69: | Línea 64: | ||
==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>Demostracion: 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 | <br> Demostracion: | ||
para B. Supongamos que tenemos una instancia para A de tamaño n. | <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 | ||
<br>Como el algoritmo de transformacion da como mucho p(n) pasos, el tamaño de | para B. | ||
la instancia del problema B es como mucho p(n). El algoritmo para B realiza como mucho q(p(n)) pasos. 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> 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>c) | |||
<br>d) | |||
<br>e) | <br>e) | ||
<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 | ||
Línea 94: | Línea 91: | ||
<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 ) | |||
Posted By Alejandro | Posted By Alejandro | ||
Línea 117: | Línea 120: | ||
==Ejercicio 11.11:== | ==Ejercicio 11.11:== | ||
<br>a) | <br>a) | ||
<br>b) | <br>b) | ||
Línea 131: | Línea 132: | ||
<br>e) | <br>e) | ||
<br>f) | <br>f) | ||
Posted By Alejandro | |||
==Ejercicio 11.12:== | ==Ejercicio 11.12:== | ||
Línea 147: | Línea 153: | ||
==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 186: | ||
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 194: | ||
<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 203: | ||
Posted By Alejandro | Posted By Alejandro | ||
==Ejercicio 11.23:== | ==Ejercicio 11.23:== | ||
<br>a) | <br>a) | ||
<br>b) | <br>b) | ||