Edición de «Práctica 11: Problemas P y NP (Algoritmos III)»

==Propiedades==
(Para todo π: Problema)

* (DEF) Un '''problema de decision''' π consiste en un conj. de instancias Dπ y un subconjunto de instancias Yπ <math>\subseteq</math> 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''' <=> π<sup>c</sup> є NP
* (DEF) π' se '''reduce polinomialmente''' a π <=> existe una f:Dπ'->Dπ tq es polinomial y (<math>\forall</math> d є Dπ') d є Yπ' <=> f(d) є Yπ. Se denota '''π' <=p π'''
* (DEF) π є '''NP-Completo''' <=>
** 1. π є NP
** 2. π є '''NP-Hard''',es decir, (<math>\forall</math> π' є NP) π' <=p π
* (TEO) P <math>\subseteq</math> NP y P <math>\subseteq</math> co-NP
* (TEO) Si P <math>\cap</math> NP-Completo <math>\neq \empty</math>, o NP-P =<math>\empty</math> -> P=NP
* (TEO) (Cook) SAT es NP-Completo

==Ejercicio 11.01:==
<br>a) Se puede hacer en O(n log n) -> esta en P
<br>b) Se puede hacer con DFS en O(n^2) -> esta en P
<br>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:==
<br>a)
<br>b)
<br>c)
==Ejercicio 11.06:==
==Ejercicio 11.07:==
<br>a)Verdadera
<br>b)Verdadera
<br>c)No se sabe
<br>d)Falso
<br>e)
<br>f)
<br>g)Falso








Posted By Alejandro

==Ejercicio 11.08:==

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

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

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

<br>Fin
<br>Posted By Alejandro

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

<br>c)Falso (No asegura que x <math> \subset </math> NP)
<br>d)Falso (No asegura que y <math> \subset </math> NP)
<br>e)
<br>f)Verdadero

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

<br>g)Falso
<br> (Hint: Ver 11.8)
<br> 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.
<br> 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:==
<br> a)Verdadero
<br>Ya que los problemas NP-Completo<math>\subset</math> NP.

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

<br>c)






Posted By Alejandro

==Ejercicio 11.11:==
<br>a)
<br>b)
<br>c)
<br>d)Verdadero:
<br>Si P<math>\neq </math>NP 
Entonces NP-Completo<math>\neq </math>  NP
<br>Y P<math>\neq </math>  NP , 
pero P<math>\cap </math> NP-Completo <math> = \emptyset </math> 


<br>e)
<br>f)




Posted By Alejandro

==Ejercicio 11.12:==
==Ejercicio 11.13:==
<br>a)
<br>b)
<br>c)(Preguntar)
<br>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:==
<br>i)	V – W es un recubrimiento de arcos de G
<br>ii)	W es un conjunto independiente de G
<br>iii)	W es un claque de Gc(complemento)

<br>a)
<br>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.
<br>
<br>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.
<br>
<br>Falta probar ii) -> iii)    
<br>
<br>b)
<br>Z1 – Mínimo recubrimiento de arcos.
<br>Z2  – Máximo conjunto independiente.
<br>Z3  – Máximo Clique.
<br>
<br>Z1 <=p Z2 <=p Z3 <=p Z1
<br><b>----(1)------(2)-----(3)--</b>
<br><b>(1)</b>
<br>IZ1(G, K1)          
<br>Iz2(G, K2)
<br>
<br>F(G, K1) = (G, n – K1)
<br>
<br>Z1(Iz1) es si <--> Z2(F(Iz1)) es si.
<br>
<br>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.
<br>
<br><b>(2)</b>F(G, K1) = (Gc, K1)
<br><b>(3)</b>F(G, K1) = (Gc, n - K1)


<br>c)

==Ejercicio 11.15:==
<b>HECHO EN CLASE, ALGUIEN QUE LO TENGA SUBALO</b>

==Ejercicio 11.16:==
==Ejercicio 11.17:==
<br>a)
<br>b)
==Ejercicio 11.18:==
==Ejercicio 11.19:==
==Ejercicio 11.20:==
==Ejercicio 11.21:==

<br> Solo serviria para ver que no me voy a matar buscando una solucion polinomial para el algoritmo(ya que es poco probable). 
<br> A lo sumo busco una buena heuristica para que me de una solucion aproximada.










Posted by Alejandro

==Ejercicio 11.22:==
<br>a)
Entonces estaria probando que los algoritmos np son polinomiales.
<br>
Si pudieramos mostrar que un problema NP-completo cualquiera
está en P, podríamos concluir que P = NP.

<br>b)
<br>
(Consultar con los ayudantes)
<br> Entonces estaria demostrando que ese problema no tiene solucion polinomica.

<br> Aunque, si este fuera NP-Completo tambien demostraria que todos los NP-Completos no tienen solucion polinomica.









Posted By Alejandro

==Ejercicio 11.23:==
<br>a)
<br>b)