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π Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \subseteq} 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 (Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \forall} d є Dπ') d є Yπ' <=> f(d) є Yπ. Se denota π' <=p π
• (DEF) π є NP-Completo <=>
  • 1. π є NP
  • 2. π є NP-Hard,es decir, (Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \forall} π' є NP) π' <=p π
• (TEO) P Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \subseteq} NP y P Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \subseteq} co-NP
• (TEO) Si P Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \cap} NP-Completo Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \neq \empty} , o NP-P =Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \empty} -> 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:

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:

a)
b)
c)

Ejercicio 11.06:

Supongamos un algoritmo polinomial no deterministico para resolver π, que tiene complejidad q(n).
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.
Luego en un algoritmo deterministico, se puede encontrar la respuesta del "oraculo" por busqueda exahustiva en Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle k^{q(n)}} pasos a lo sumo.
Finalmente la complejidad del algoritmo deterministico es de Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle q(n)*k^{q(n)}} quien se puede acotar por Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle 2^{p(n)}} .

Ejercicio 11.07:

a)Verdadera
b)Verdadera
c)Falso
d)Falso
e)Falso
f)Verdadero
g)Falso

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 Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \subset } NP)

d)Falso (No asegura que y Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \subset } 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-CompletoError al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \subset} NP.

b)Falso
No esta demostrado que NP=NP-Hard,
Si, que NP-CompletoError al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \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:

Si P != NP, entonces todo problema NP (los NP-completos en particular) no tienen una solucion polinomial.

a)
b)
c)
d)Verdadero:
Si PError al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \neq } NP Entonces NP-CompletoError al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \neq } NP
Y PError al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \neq } NP , pero PError al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \cap } NP-Completo Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle = \emptyset }

e)
f)

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:

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:

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.

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

Otra consecuencia es que ese alguien seria acreedor de 1x10^6 dolares!!

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.

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
Powered By Login2Edit

Ejercicio 11.23:

a)
b)