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

De Cuba-Wiki

Propiedades

(Para todo π: Problema)

  • (DEF) Un problema de decision π consiste en un conj. de instancias Dπ y un subconjunto de instancias Yπ Dπ cuya respuesta es SI
  • (DEF) π є P <=> existe una DTM polinomial que resuelve π
  • (DEF) π є NP <=> existe una NDTM polinomial que resuelve π (para toda instancia Yπ, alguna de las ramas termina en Qsi en tiempo polinomial)
  • (DEF) π є co-NP <=> πc є NP
  • (DEF) π' se reduce polinomialmente a π <=> existe una f:Dπ'->Dπ tq es polinomial y ( d є Dπ') d є Yπ' <=> f(d) є Yπ. Se denota π' <=p π
  • (DEF) π є NP-Completo <=>
    • 1. π є NP
    • 2. π є NP-Hard,es decir, ( π' є NP) π' <=p π
  • (TEO) P NP y P co-NP
  • (TEO) Si P NP-Completo , o NP-P = -> P=NP
  • (TEO) (Cook) SAT es NP-Completo

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





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)Falso (No asegura que x NP)


d)Falso (No asegura que y NP)


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 NP.


b)Falso
No esta demostrado que NP=NP-Hard,
Si, que NP-CompletoNP-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 PNP Entonces NP-Completo NP
Y P NP , pero P NP-Completo



e)
f)



Posted By Alejandro

Ejercicio 11.12:

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:


i) V – W es un recubrimiento de arcos de G
ii) W es un conjunto independiente de G
iii) W es un claque de Gc(complemento)


a)
i) -> ii) Sup. que no. Entonces V – W no es un conjunto independiente -> EXISTE e perteneciente a X / e = (w1,w2) y w1, w2 pertenecen W -> w1, w2 no pertenecen W - V -> V - W no es recubrimiento de ejes por que no recubre a e.

ii) -> i) Sup. que no. Entonces V – W no es rec. de arcos -> EXISTE e perteneciente a X / e = (w1,w2) y w1, w2 no pertenecen V –W -> w1, w2 pertenecen W -> w1, w2 pertenecen a un conjunto independiente. ABS por que están unidos por un eje.

Falta probar ii) -> iii)

b)
Z1 – Mínimo recubrimiento de arcos.
Z2 – Máximo conjunto independiente.
Z3 – Máximo Clique.

Z1 <=p Z2 <=p Z3 <=p Z1
----(1)------(2)-----(3)--
(1)
IZ1(G, K1)
Iz2(G, K2)

F(G, K1) = (G, n – K1)

Z1(Iz1) es si <--> Z2(F(Iz1)) es si.

Existe un rec. de ejes de K1 nodos y H es ese conjunto <--> V – H es un conjunto independiente <--> existe un conjunto independiente n – K1 <--> Z2(F(Iz1)) es si.

(2)F(G, K1) = (Gc, K1)
(3)F(G, K1) = (Gc, n - K1)



c)

Ejercicio 11.15:

HECHO EN CLASE, ALGUIEN QUE LO TENGA SUBALO (por favor)

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)