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)Verdadera
b)Verdadera
c)No se sabe
d)Falso
e)
f)
g)Falso

Posted By Alejandro

Ejercicio 11.08:

ES cierto. Justamente la relacion de reducibilidad dice: Si existe un algoritmo de transformacion polinomico del problema de decision A en el problema de decision B, el problema A es reducible polinomicamente al problema B. Lo denotamos: A <=p B.

Ademas sabemos que un problema B es NP-completo si:
1. esta en NP, y
2. para cualquier otro problema A en NP, A <=p B.

Ya que existe una transformacion polinomica para reducir el algoritmo X a Y, de igual forma Y a X.
Con lo cual , llamemos A=X, B=Y, entonces se cumple que X <=p Y, luego
Sea A=Y,B=X, entonces se cumple que X <=p Y.

Fin
Posted By Alejandro

Ejercicio 11.09:

a)Falso
b)Si el problema de decision Y esta en P y X <=p Y, entonces el problema de decision X 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.

c)
d)
e)
f)Verdadero

Un problema C es NP-completo si
1. esta en NP, y
2. para algun problema NP-completo B, B <=p C.
Demostracion:
Por ser B NP-completo, para cualquier problema A en NP, A <=p B.
• La reducibilidad es transitiva. Por tanto, A <=p C.
• Ya que C esta en NP, concluimos que C es NP-completo.

g)Falso
(Hint: Ver 11.8)
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 )

Posted By Alejandro

Ejercicio 11.10:

a)Verdadero
Ya que los problemas NP-Completo$\subset$ NP.

b)Falso
No esta demostrado que NP=NP-Hard,
Si, que NP-Completo$\subset$NP-Hard.
Habria que probar que todos los Problemas NP-Dificiles se resuelven en tiempo polinomial(Lo veo poco probable).

c)

Posted By Alejandro

Ejercicio 11.11:

a)
b)
c)
d)Verdadero:
Si P$\neq$NP Entonces NP-Completo$\neq$ NP
Y P$\neq$ NP , pero P$\cap$ NP-Completo $=\emptyset$

e)
f)

Posted By Alejandro

Ejercicio 11.13:

a)
b)
c)(Preguntar)
Primero habria que verificar si es NP-Completo, luego si esto sucede, se podria reducir usando SAT, para resolver TSP.

Posted By Alejandro

Ejercicio 11.14:

a)
b)
c)

Ejercicio 11.17:

a)
b)

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)