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 69: | Línea 69: | ||
==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)Falso (No asegura que x <math> \subset </math> NP) | <br>c)Falso (No asegura que x <math> \subset </math> NP) | ||
<br>d)Falso (No asegura que y <math> \subset </math> NP) | <br>d)Falso (No asegura que y <math> \subset </math> NP) | ||
<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 96: | ||
<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 |