Práctica 12: 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π $\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 ($\forall$ d є Dπ') d є Yπ' <=> f(d) є Yπ. Se denota π' <=p π
• (DEF) π є NP-Completo <=>
  • 1. π є NP
  • 2. π є NP-Hard,es decir, ($\forall$ π' є NP) π' <=p π
• (TEO) P $\subseteq$ NP y P $\subseteq$ co-NP
• (TEO) Si P $\cap$ NP-Completo $\neq \emptyset$, o NP-P =$\emptyset$ -> P=NP
• (TEO) (Cook) SAT es NP-Completo

Ejercicio 12.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 12.02:

Vale porque la composicion de reducciones polinomiales es una reduccion polinomial

Ejercicio 12.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 12.05:

a)
b)
c)

Ejercicio 12.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 $k^{q(n)}$ pasos a lo sumo.
Finalmente la complejidad del algoritmo deterministico es de $q(n)*k^{q(n)}$ quien se puede acotar por $2^{p(n)}$.

Ejercicio 12.07:

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

Ejercicio 12.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 12.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 $\subset$ NP)

d)Falso (No asegura que y $\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 12.10:

a)Verdadero
Ya que los problemas NP-Completo$\subset$ NP.

b)Falso
No esta demostrado que NP=NP-Hard,
Si, que NP-Completo$\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 12.11:

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

a)
b)
c)
d)Verdadero:
Si P$\neq$NP Entonces NP-Completo$\neq$ NP
Y P$\neq$ NP , pero P$\cap$ NP-Completo $=\emptyset$

e)
f)

Ejercicio 12.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 12.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 12.15:

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

Ejercicio 12.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 12.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 12.18:

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

Ejercicio 12.19:

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

Ejercicio 12.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 12.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 12.23:

a)
b)