Diferencia entre revisiones de «Práctica 11: Problemas P y NP (Algoritmos III)»
Línea 15: | Línea 15: | ||
==Ejercicio 11.06:== | ==Ejercicio 11.06:== | ||
==Ejercicio 11.07:== | ==Ejercicio 11.07:== | ||
<br>a) | <br>a)Verdadera | ||
<br>b) | <br>b)Verdadera | ||
<br>c) | <br>c)No se sabe | ||
<br>d) | <br>d)Falso | ||
<br>e) | <br>e) | ||
<br>f) | <br>f) | ||
<br>g) | <br>g)Falso | ||
==Ejercicio 11.08:== | ==Ejercicio 11.08:== | ||
==Ejercicio 11.09:== | ==Ejercicio 11.09:== |
Revisión del 18:08 29 nov 2006
Ejercicio 11.01:
a) Se puede hacer en O(n log n) -> esta en P
b) Se puede hacer con DFS en O(n^2) -> esta en P
c) Se puede hacer con DFS en O(n^2) -> esta en P
Ejercicio 11.02:
Vale porque la composicion de reducciones polinomiales es una reduccion polinomial
Ejercicio 11.03:
Ejercicio 11.04:
Ejercicio 11.05:
a)
b)
c)
Ejercicio 11.06:
Ejercicio 11.07:
a)Verdadera
b)Verdadera
c)No se sabe
d)Falso
e)
f)
g)Falso
Ejercicio 11.08:
Ejercicio 11.09:
a)
b)
c)
d)
e)
f)
g)
Si el problema de decision B esta en P y A <=p B, entonces el
problema de decision A esta en P.
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
para B.
Supongamos que tenemos una instancia para A de tamaño n.
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).
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.
Posted By Alejandro
Ejercicio 11.10:
a)
b)
c)
Ejercicio 11.11:
a)
b)
c)
d)
e)
f)
Ejercicio 11.12:
Ejercicio 11.13:
a)
b)
c)
Ejercicio 11.14:
a)
b)
c)
Ejercicio 11.15:
Ejercicio 11.16:
Ejercicio 11.17:
a)
b)
Ejercicio 11.18:
Ejercicio 11.19:
Ejercicio 11.20:
Ejercicio 11.21:
Solo serviria para ver que no me voy a matar buscando una solucion polinomial para el algoritmo(ya que es poco probable).
A lo sumo busco una buena heuristica para que me de una solucion aproximada.
Posted by Alejandro
Ejercicio 11.22:
a)
Entonces estaria probando que los algoritmos np son polinomiales.
Si pudieramos mostrar que un problema NP-completo cualquiera
está en P, podríamos concluir que P = NP.
b)
(Consultar con los ayudantes)
Entonces estaria demostrando que ese problema no tiene solucion polinomica.
Aunque, si este fuera NP-Completo tambien demostraria que todos los NP-Completos no tienen solucion polinomica.
Posted By Alejandro
Ejercicio 11.23:
a)
b)