Práctica 11: Problemas P y NP (Algoritmos III)

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.05:

a)
b)
c)

Ejercicio 11.07:

a)
b)
c)
d)
e)
f)
g)

Ejercicio 11.09:

a)
b)
c)
d)
e)
f)
g)

Ejercicio 11.10:

a)
b)
c)

Ejercicio 11.11:

a)
b)
c)
d)
e)
f)

Ejercicio 11.13:

a)
b)
c)

Ejercicio 11.14:

a)
b)
c)

Ejercicio 11.17:

a)
b)

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)