Diferencia entre revisiones de «Práctica 11: Problemas P y NP (Algoritmos III)»

De Cuba-Wiki
Línea 31: Línea 31:
<br>f)
<br>f)
<br>g)
<br>g)
Si el problema de decision B esta en P y A <=p B, entonces el
problema de decision A esta en P.
<br>Demostraci´on:
<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.
Posted By Alejandro
==Ejercicio 11.10:==
==Ejercicio 11.10:==
<br>a)
<br>a)

Revisión del 23:37 28 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)
b)
c)
d)
e)
f)
g)

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.



Demostraci´on:
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:

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.






Posted By Alejandro

Ejercicio 11.23:


a)
b)