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

{{Back|Algoritmos y Estructuras de Datos 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:==
Ver
http://en.wikipedia.org/wiki/Clique_problem#Cliques_of_fixed_size

O(n^k * k^2) y con k=4 (constante) queda O(n^4) con lo cual está en P y en NP.

==Ejercicio 11.04:==
Mi practica 2 llega hasta el ejercicio 22!!! Que onda?

==Ejercicio 11.05:==
<br>a)
<br>b)
<br>c)
==Ejercicio 11.06:==

Supongamos un algoritmo polinomial no deterministico para resolver π, que  tiene complejidad q(n).
<br>Entonces para toda entrada el "oraculo" que adivina del algoritmo no deterministico  devuelve una respuesta de longitud q(n) (si ocupa menos se la completa con ceros) con un alfabeto de k letras.
<br>Luego en un algoritmo deterministico, se puede encontrar la respuesta del "oraculo" por busqueda exahustiva en <math> k^{q(n)}</math> pasos a lo sumo. <br>Finalmente la complejidad del algoritmo deterministico es de <math> q(n)*k^{q(n)}</math> quien se puede acotar por <math> 2^{p(n)}</math>.

==Ejercicio 11.07:==
<br>a)Verdadera
<br>b)Verdadera
<br>c)Falso
<br>d)Falso
<br>e)Falso
<br>f)Verdadero
<br>g)Falso

==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: 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.
<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). 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.

<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. 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:==
Si P != NP, entonces todo problema NP (los NP-completos en particular) no tienen una solucion polinomial.

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


<br>e)
<br>f)

==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 (por favor)</b>

==Ejercicio 11.16:==
Solo se puede decir que es NP-Hard, a menos que probemos que pertenece a NP, si lo probamos entraria en la categoria NP-Completo

==Ejercicio 11.17:==

<br>a) Es NP-Completo. 

Probar que es NP es facíl, con DFS chequeo el camino
Probar completitud, sólo tenemos que definir la transformación en vez de que el camino tenga longitud k definimos que tenga en n y usamos circuito hamiltoniano.
La demostración de que una instancia de cto hamiltoniano da SI <=> la transformación de camino hamiltoniano da SI es simplemente como actua la transformación.

<br>b) Es P, lo podemos hacer tomando todos los subconjuntos de 8 nodos en un poco menos de n^8.... Sigue siendo polinomial!

También se puede elevar la matriz de adyacencia a la 8 y con esto obtener todos los caminos de longitud al menos 8. (ver 
http://en.wikipedia.org/wiki/Adjacency_matrix#Properties)

==Ejercicio 11.18:==

Se puede demostrar facilmente usando TSP que ya sabemos que es NP Completo

==Ejercicio 11.19:==
Resuelve SAT  . Usar la siguiente formula :  FormulaOriginal Y (q o no q).
Con q variable fresca.

==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>
<br> Otra consecuencia es que ese alguien seria acreedor de 1x10^6 dolares!!

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

<br> Si no me equivoco, tambien estaria demostrando que NP no esta incluído en P, ya que existe un problema intratable en NP, por lo tanto no puede pertenecer a P, esto significa que P!=NP.. y ese alguien "otra vez" seria acreedor de 1x10^6 dolares.. ¬¬






Posted By Alejandro
<br>Powered By Login2Edit

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


[[Category: Prácticas]]