| Revisión actual |
Tu texto |
| Línea 1: |
Línea 1: |
| {{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:== | | ==Ejercicio 11.01:== |
| <br>a) Se puede hacer en O(n log n) -> esta en P | | <br>a) Se puede hacer en O(n log n) -> esta en P |
| Línea 25: |
Línea 8: |
|
| |
|
| ==Ejercicio 11.03:== | | ==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:== | | ==Ejercicio 11.04:== |
| Mi practica 2 llega hasta el ejercicio 22!!! Que onda?
| |
|
| |
| ==Ejercicio 11.05:== | | ==Ejercicio 11.05:== |
| <br>a) | | <br>a) |
| Línea 38: |
Línea 14: |
| <br>c) | | <br>c) |
| ==Ejercicio 11.06:== | | ==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:== | | ==Ejercicio 11.07:== |
| <br>a)Verdadera | | <br>a)Verdadera |
| <br>b)Verdadera | | <br>b)Verdadera |
| <br>c)Falso | | <br>c)No se sabe |
| <br>d)Falso | | <br>d)Falso |
| <br>e)Falso | | <br>e) |
| <br>f)Verdadero | | <br>f) |
| <br>g)Falso | | <br>g)Falso |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | Posted By Alejandro |
|
| |
|
| ==Ejercicio 11.08:== | | ==Ejercicio 11.08:== |
| Línea 70: |
Línea 50: |
| <br>a)Falso | | <br>a)Falso |
|
| |
|
| <br>b)Si el problema de decision Y esta en P y X <=p Y, entonces el | | <br>b) Si el problema de decision Y esta en P y X <=p Y, entonces el |
| problema de decision X esta en P. | | 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> 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) |
|
| |
|
| <br>d)Falso (No asegura que y <math> \subset </math> NP) | | <br>d) |
|
| |
|
| <br>e) | | <br>e) |
|
| |
|
| <br>f)Verdadero | | <br>f)Verdadero |
| | |
| <br>Un problema C es NP-completo si | | <br>Un problema C es NP-completo si |
| <br>1. esta en NP, y | | <br>1. esta en NP, y |
| <br>2. para algun problema NP-completo B, B <=p C. | | <br>2. para algun problema NP-completo B, B <=p C. |
| | |
| <br>Demostracion: | | <br>Demostracion: |
| <br> Por ser B NP-completo, para cualquier problema A en NP, A <=p B. | | <br> Por ser B NP-completo, para cualquier problema A en NP, A <=p B. |
| Línea 94: |
Línea 83: |
| <br>g)Falso | | <br>g)Falso |
| <br> (Hint: Ver 11.8) | | <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 ) | | <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 | | Posted By Alejandro |
| Línea 117: |
Línea 112: |
|
| |
|
| ==Ejercicio 11.11:== | | ==Ejercicio 11.11:== |
| Si P != NP, entonces todo problema NP (los NP-completos en particular) no tienen una solucion polinomial.
| |
|
| |
| <br>a) | | <br>a) |
| <br>b) | | <br>b) |
| Línea 131: |
Línea 124: |
| <br>e) | | <br>e) |
| <br>f) | | <br>f) |
| | |
| | |
| | |
| | |
| | Posted By Alejandro |
|
| |
|
| ==Ejercicio 11.12:== | | ==Ejercicio 11.12:== |
| Línea 147: |
Línea 145: |
|
| |
|
| ==Ejercicio 11.14:== | | ==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>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>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) | | <br>c) |
|
| |
| ==Ejercicio 11.15:== | | ==Ejercicio 11.15:== |
| <b>HECHO EN CLASE, ALGUIEN QUE LO TENGA SUBALO (por favor)</b>
| |
|
| |
| ==Ejercicio 11.16:== | | ==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:== | | ==Ejercicio 11.17:== |
| | | <br>a) |
| <br>a) Es NP-Completo. | | <br>b) |
| | |
| 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:== | | ==Ejercicio 11.18:== |
|
| |
| Se puede demostrar facilmente usando TSP que ya sabemos que es NP Completo
| |
|
| |
| ==Ejercicio 11.19:== | | ==Ejercicio 11.19:== |
| Resuelve SAT . Usar la siguiente formula : FormulaOriginal Y (q o no q).
| |
| Con q variable fresca.
| |
|
| |
| ==Ejercicio 11.20:== | | ==Ejercicio 11.20:== |
| ==Ejercicio 11.21:== | | ==Ejercicio 11.21:== |
| Línea 231: |
Línea 178: |
| Si pudieramos mostrar que un problema NP-completo cualquiera | | Si pudieramos mostrar que un problema NP-completo cualquiera |
| está en P, podríamos concluir que P = NP. | | 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>b) |
| Línea 241: |
Línea 186: |
| <br> Aunque, si este fuera NP-Completo tambien demostraria que todos los NP-Completos no tienen 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.. ¬¬
| | |
| | |
|
| |
|
|
| |
|
| Línea 249: |
Línea 195: |
|
| |
|
| Posted By Alejandro | | Posted By Alejandro |
| <br>Powered By Login2Edit
| |
|
| |
|
| ==Ejercicio 11.23:== | | ==Ejercicio 11.23:== |
| <br>a) | | <br>a) |
| <br>b) | | <br>b) |
|
| |
|
| |
| [[Category: Prácticas]]
| |
