# Complejidad De Problemas (P, NP, NPC, NP-Hard)
###### tags: `temas 2do Parcial`

## Resumen

### Glosario/definiciones

* **e**uleriano: pasa por todos los **e**jes

* hamiltoniano: pasa por todos los nodos

* recorrido: sucesión de vértices y aristas dentro de un grafo, que empieza y termina en vértices, tal que cada vértice es incidente con las aristas que le siguen y le preceden en la secuencia

* camino: recorrido sin aristas repetidas

* Forma normal disyuntiva: OR de ANDs

* Tautología: Fórmula que siempre es cierta

* $Π' ≤_p Π$: existe $f$ tal que $Π' ∈ Y <=> f(Π') ∈ Y_Π$ (abuso de notación: no son los problemas Π y Π', sino instancias de los mismos)

* Teorema de Cook-levin:

* $Π ∈ NPC$

* $Γ ∈ NP$

* $Π ≤_p Γ$

* $=> Γ ∈ NPC$

* NP-hard: Π ∈ Np-hard $<=> ∀ Γ ∈ NP, Γ ≤_p Π$

* NPC: NP y NP-hard

### Cómo dar certificado positivo polinomial verificable en tiempo polinomial

* Deberían no ser más de 3 oraciones la respuesta:
1. El certificado es así.
2. El certificador revisa estas cosas.
3. "Es fácil ver que esto se puede hacer en tiempo polinomial". En casos raros, la oración 3 se reemplaza por un algoritmo que muestre que eso es polinomial.

### Trucos

* Contrarrecíproco: Si no me sale demostrar P $=>$ Q, ver si puedo ¬Q $=>$ ¬P (Ej 15c)

* Ej 18. Dividir un nodo v en v_in y v_out. Util cuando necesitamos pesos en los nodos o camino hamiltoniano.

* Ej 20. Si probar algo de un grafo es complicado, fijate si podés probar lo que ocurre en el complemento.

### Errores comunes

* Olvidarse del $k$ cuando tenemos un problema de decisión

### Problemas conocidos
* TSP. NPC
* SAT, NPC

## Ejercicios de guías

### 1. Para cada uno de los siguientes problemas:

* 1.1 Proponer un certificado **de tamaño polinomial** de cada instancia positiva **que se pueda verficar en tiempo polinomial**. En caso que el problema sea polinomial, el certificado debe ser distinto a la instancia.

* 1.2 Describir claramente cómo funciona el verificador correspondiente

#### c) MAXFLOW: dada una red N con fuente s y sumidero t y un natural f, ¿N tiene un fujo de valor mayor o igual a f?

* Certificado: Un conjunto de tuplas (arista, flujo) que contiene para cada arista el flujo que pasa por ella

* El certificador revisa:
* que las aristas pertenezcan a la red,
* que el flujo que pasa por ellas sea <= a su capacidad,
* que se cumpla la conservación de flujo en todos los vértices.
* que el flujo que llega al sumidero t sea mayor o igual al flujo f recibido por input

“Es fácil ver que esto se puede hacer en tiempo polinomial” -- souli
(revisa las aristas en O(m))

#### d) SHORTEST PATH (SP): dado un digrafo pesado G, dos vértices s y t, y un natural k ¿G tiene un recorrido de s a t de peso menor o igual a k?

* Certificado: Secuencia de a lo sumo |E(G)| aristas que forman un recorrido de s a t

* El certificador revisa:
* que los arcos pertenezcan al grafo
* que el primer arco una a s con algún otro nodo, y la última llegue a t
* que para cada arco de la secuencia se cumpla que el nodo de destino de la anterior sea igual al nodo de origen de la siguiente (menos para el primero, ya que no tiene un "arco anterior" en el recorrido)
* que la suma de los pesos del recorrido sea menor o igual a k

“Es fácil ver que esto se puede hacer en tiempo polinomial” -- souli
(cada uno de los pasos del certificador se pueden hacer en O(m))

#### f) HAMPATH: dado un digrafo G y dos vértices s y t ¿G tiene un camino de s a t que pase por todos los vértices de G?

* Certificado: Secuencia de a lo sumo |E(G)| aristas que forman un camino de s a t

* El certificador revisa:
* que los arcos pertenezcan al grafo y no hay arcos repetidos
* que el primer arco una a s con algún otro nodo, y la última llegue a t
* que para cada arco de la secuencia se cumpla que el nodo de destino de la anterior sea igual al nodo de origen de la siguiente (menos para el primero, ya que no tiene un "arco anterior" en el recorrido)
* que todos los vértices de G estén en el camino

“Es fácil ver que esto se puede hacer en tiempo polinomial” -- souli
(los primeros pasos del certificador se pueden hacer en O(m), mientras que el último se puede hacer en O(n))

#### h) k-CLIQUE: dado un grafo G, ¿G tiene un subgrafo completo de tamaño mayor o igual a k? (Nota: son infinitos problemas, uno por cada k.)

* respuesta: si (porque es una instancia positiva)

* certificado (cómo lo demostramos): la clique: conjunto de k vértices

* certificador (cómo lo verifican):
* que el certificado tenga tamaño k o más
* que los vértices del certificado estén en el grafo (pertenezcan a V(G)) (O(n))
* para cada vértice del conjunto: // O(n² x m)
* verifico que haya una arista en E(G) que lo conecte con los otros k-1 vértices del certificado

“Es fácil ver que esto se puede hacer en tiempo polinomial” -- souli

#### i) CLIQUE: dado un grafo G y un natural k, ¿G tiene un completo de tamaño mayor o igual a k?

### 2. Para cada uno de los siguientes problemas:
* 2.1 Proponer un **certificado** de tamaño **polinomial** de cada instancia **negativa que se pueda verificar en tiempo polinomial**.

* En caso que el problema sea polinomial, el certificado debe ser distinto a la instancia. Describir claramente cómo funciona el verificador correspondiente.

#### e) k-CLIQUE: ver ejercicio anterior.

#### f) TAUTOLOGY: dada una formula proposicional (en forma normal disyuntiva) φ, ¿es φ una tautología?

* Respuesta: no (por ser instancia negativa)

* Certificado: una asignación de variables (tamaño: cantidad de variables) tal que la fórmula evalue a falso

* Certificador:
* asignar las variables
* evaluar la fórmula
* verificar que de falso

“Es fácil ver que esto se puede hacer en tiempo polinomial” -- souli

### 7. Considerar los siguientes problemas:

* 2-PARTITION: dado un conjunto de naturales X con $min\{X\} > 2$, ¿existe S ⊆ X tal que $∑S = ∑ x/2$?

* 3-PARTITION: dado un conjunto de naturales $X = {x_1, ... , x_{3n}}$ con $∑X = nt$, 0 < mín X y máx X < bt/2c, ¾se puede particionar X en n triplas que sumen t?

* RECTANGLE PACKING: dado un rectángulo grande r y una familia de rectángulos pequeños R = {r1, . . . , rn}, ¾se pueden ubicar todos los ri dentro de r (permitiendo rotaciones) sin que se solapen? (Nota: un rectángulo se codifica en la computadora usando un par de números.)

a) Dada una instancia X de 2-PARTITION, se dene la instancia 〈r, R〉 de RECTANGLE PACKING donde r tiene base ∑ X/2 y altura 2 y R tiene un rectángulo de base x y altura 1 para todo x ∈ X. Demostrar que X es una instancia positiva de 2-PARTITION si y solo si 〈r, R〉 es una instancia positiva de RECTANGLE PACKING.

b) Dada una instancia X de 3-PARTITION, se dene la instancia 〈r, R〉 de RECTANGLE PACKING donde r tiene base n y altura t + 3n y R tiene un rectángulo de base 1 y altura n + x para cada x ∈ X. Demostrar que X es una instancia positiva de 3-PARTITION si y solo si 〈r, R〉 es una instancia positiva de RECTANGLE PACKING.

c) Mostrar que las reducciones implicadas por los puntos anteriores son polinomiales en función de los tamaños de las entradas.

### 12. Determinar cuáles de las siguientes afirmaciones son verdaderas y cuáles falsas. Demostrar aquellas que son verdaderas y dar contraejemplos para aquellas que son falsas

#### a) P ⊆ NP y P ⊆ coNP.

* Si un problema está en P, entonces puedo resolverlo en tiempo polinomial. Por ende, puedo crear un certificado de tamaño polinomial (el trivial: la instancia misma), así como también verificarlo en tiempo polinomial (usando el algoritmo que lo resuelve en tiempo polinomial). Por ende, está en NP.

* El caso de coNP es análogo. Como tengo un algoritmo que lo resuelve en tiempo polinomial, dada una instancia negativa (que puedo usar como certificado) puedo verificarla usando tal algoritmo.

#### b) Si P = NP, entonces coNP = NP.

V

P = NP => si lo puedo certificar en tiempo polinomial, lo puedo resolver en tiempo polinomial

coNP = NP => P = coNP

Para cualquier instancia positiva o negativa voy a poder crear un certificado polinomial (el trivial) así como también verificarlo en tiempo polinomial usando el algoritmo que lo resuelve (por ser P) (análogo al subpunto anterior).

#### c) Si P = NP, entonces todos los problemas computacionales pertenecen a P.

Falso

Hay otras clases de problemas: ExpTime. Hay problemas que no pueden ser siquiera verificados en tiempo polinomial o no podemos dar un certificado de tamaño polinomial. NP-hard tampoco está contenida en P, ni en NP (por ejemplo, el problema de suma de subconjuntos).

#### d) Si coNP = NP, entonces SAT ∈ coNP.

Verdadero

coNP = NP => para todo problema tal que para toda instancia positiva puedo certificarla y verificarla polinomialmente, puedo también hacerlo para instancias negativas y viceversa
vos
Entonces, como sabemos que SAT está en NPC => está en NP

==> asumiendo coNP = NP, podríamos certificar y verificar instancias negativas de SAT en tiempo polinomial, por lo que SAT también pertenecería a coNP.

#### e) Si coNP ⊆ NP, entonces NP = coNP

Verdadero

coNP ⊆ NP => para todo problema tal que para toda instancia negativa puedo certificarla y verificarla polinomialmente, puedo también hacerlo para instancias positivas

$∀ Π ∈ NP, Π^c ∈ CoNP ⇒ Π^c ∈ NP$ (este último paso por hipótesis)

Como $Π^c ∈ NP ⇒ (Π^c)^c ∈ coNP$ (si podía verificar polinomialmente instancias positivas e invertí el problema, ahora puedo verificar polinomialmente instancias negativas)

Como $(Π^c)^c = Π ⇒ Π ∈ coNP$

$⇒ ∄ Π ∈ NP$ tal que $Π ∉ CoNP$

$∴ NP = CoNP$

### 13. Es cierto que si dos problemas $Π$ y $Γ$ pertenecen a $NPC$ entonces $Π ≤_p Γ$, y también $Γ ≤_p Π$? Justificar.

$Π, Γ ∈ NPC ⇒$

$i) Π, Γ ∈ NP$
$ii)$ Para todo problema $NP$, el mismo se puede reducir polinomialmente a $Π$ y a $Γ$

Por ii, en particular, $Π ≤_p Γ$ y $Γ ≤_p Π$

### 14. Sean $Π$ y $Γ$ dos problemas de decisión tales que $Π ≤_p Γ$. ¿Qué se puede inferir?

$Π ≤_p Γ$:

existe $f$ tal que $Π ∈ Y <=> f(Π) ∈ Y_Γ$

(abuso de notación: no son los problemas Γ y Π, sino instancias de los mismos)

#### a) Si $Π ∈ P$ entonces $Γ ∈ P$.

Falso

Como $Π ≤_p Γ$,

Existe $f$ tal que $Π ∈ Y <=> f(Π) ∈ Y_Γ$

No puedo inferir nada sobre la complejidad de Γ. Si bien $Π ∈ P$, $Y_Γ$ puede ser NP.

f podría transformar a Π en una instancia de un problema más difícil en tiempo polinomial.

#### b) Si $Γ ∈ P$ entonces $Π ∈ P$.

Verdadero

Como $Π ≤_p Γ$,

Existe $f$ tal que $Π ∈ Y <=> f(Π) ∈ Y_Γ$

Para resolver una instancia de Π, puedo reducirla a una instancia de $Γ$ en tiempo polinomial, y luego usar el algoritmo polinomial que resuelve instancias de $Γ$ y devolver la respuesta.

Por ende, $Π ∈ P$.

#### c) Si $Γ ∈ NPC$ entonces $Π ∈ NPC$.

Hipótesis: $Π ≤_p Γ ∧ Γ ∈ NPC$

Teorema de Cook-levin:

* $Π ∈ NPC$

* $Γ ∈ NP ∧ Π ≤_p Γ$

* $=> Γ ∈ NPC$

No nos sirve Cook-Levin porque no podemos asumir que $Π ∈ NP$: No sabemos si podemos dar un certificado polinomial, ni si podríamos verificarlo en tiempo polinomial tampoco (pues por más que transformásemos una instancia de Π en Γ, Γ solo sabemos que es NPC. En ppio no hay algo poli para resolver Γ.)

#### d) Si $Π ∈ NPC$ entonces $Γ ∈ NPC$.

Hipótesis: $Π ≤_p Γ$

Cook-Levin:

* $Π ∈ NPC$ OK

* $Γ ∈ NP$ no podemos suponerlo

* $Π ≤_p Γ$ OK

* $=> Γ ∈ NPC$

Falso. No podemos asumir que $Γ ∈ NP$.

#### e) Si $Γ ∈ NPC$ y $Π ∈ NP$ entonces $Π ∈ NPC$.

Hipótesis: $Π ≤_p Γ$

Cook-Levin:

* $Π ∈ NPC$

* $Γ ∈ NP$

* $Π ≤_p Γ$

* $=> Γ ∈ NPC$

Con las hipótesis del problema **no** se puede inferir que $Π ∈ NPC$.

#### f) Si $Π ∈ NPC$ y $Γ ∈ NP$ entonces $Γ ∈ NPC$.

Hipótesis: $Π ≤_p Γ$

Verdadero por Cook-Levin:

* $Π ∈ NPC$

* $Γ ∈ NP$

* $Π ≤_p Γ$

* $=> Γ ∈ NPC$

#### g) $Π$ y $Γ$ no pueden pertenecer ambos a $NPC$.

Falso. Ambos podrían estar en $NPC$.

### 15. Decir si las siguientes oraciones son verdaderas o falsas:

#### a) Si P = NP, entonces todo problema NP-completo es polinomial.

Verdadero

NPC: NP y NP-hard.

En particular, todo problema NPC es $NP =_{\text{por hipótesis}} P$.

Por lo tanto todo problema NPC es polinomial.

#### b) Si P = NP, entonces todo problema NP-hard es polinomial.

Falso

NP-hard: $Π ∈ NPhard <=> ∀ Γ ∈ NP, Γ ≤_p Π$

No podemos asumir a partir de P = NP que exista un algoritmo polinomial para un problema NP-hard arbitrario (solo para los que estén en NPC).

#### c) Si las clases NP-completo y coNP-completo son disjuntas entonces P ≠ NP.

Verdadero

NPC:
i) NP: puedo cert y verif inst pos en tiempo poli
ii) NP-hard

coNPC:
i) coNP: puedo cert y verif inst neg en tiempo poli
ii) coNP-hard


Sale por contrarrecíproco usando el resultado del ejercicio 12) b).

### 17. Sabiendo que CLIQUE es NP-completo, demostrar que SUBGRAPH ISOMORPHISM es NP-completo.

CLIQUE: dado un grafo G y un natural k, ¿G tiene un completo de tamaño mayor o igual a k?

SUB. ISO.: dados dos grafos G y H, ¿es H isomorfo a un subgrafo inducido de G?

Subgrafo: $V′ ⊆ V ∧ E′ ⊆ E$

Subgrafo inducido: con menos vértices, pero se conservan todas las aristas posibles.

Clique ∈ NPC, qvq SUB. ISO. ∈ NPC

Vamos a usar Cook-Levin. Qvq:

i) SUB. ISO. ∈ NP
ii) CLIQUE $≤_p$ SUB. ISO. .

#### i) Qvq para cualquier instancia positiva de SUB. ISO. podemos dar un certificado polinimial verificable en tiempo polinomial

* Certificado posible: Conjunto de pares de vértices $(v_g, v_h)$ tales que $v_g ∈ G$ y $v_h ∈ H$ de forma tal que cada tupla corresponde al nombre de un mismo vértice en G y en H

CONSULTAR: si dar los pares $(g, h)$ de ejes tales que $g ∈ G$ y $h ∈ H$ también funciona

* Verificador:

* Iterar los vértices de G renombrando según el certificado y borrando los que no aparezcan en él
* Iterar las aristas de G borrando las que involucren algún vértice de G que no aparezca en el certificado
* Verificamos $V(G) == V(H) ∧ E(G) == E(H)$

* Es fácil ver que esto es polinomial

#### ii) Clique $≤_p$ S.I.

* Para ver que $Clique ≤_p S.I.$, queremos ver que:
* existe $f$ tal que $Clique ∈ Y <=> f(Clique) ∈ Y_{S.I.}$ (abuso de notación: no son los problemas S.I. y Clique, sino instancias de los mismos)

La $f$ que podemos utilizar es una que tranforme (G, n) en (G, $K_n$), siendo $K_n$ un subgrafo completo de tamaño n. f(G,n) = (G, H = Kn)

$=>$)

Asumiendo que tengo una instancia (G, n) de Clique ∈ Y, QVQ existe $f$ tal que f(Clique) ∈ Y_{S.I.}$

Si (G, n) ∈ Y, entonces significa que hay un $K_n$ adentro de G, por lo que S.I también ∈ Y.

$=>$)

Asumiendo que tengo una instancia de $f(Clique) ∈ Y_{S.I.}$, QVQ $Clique ∈ Y$

Como (G, $K_n$) $∈ Y_{S.I.}$, entonces significa que G tiene adentro un $K_n$, por lo que la instancia correspondiente de Clique a ese $n$ también ∈ Y.

### 18. Sabiendo que HAMPATH es NP-completo, demostrar que ELEMENTARY SHORTEST PATH es NPC.

HAMPATH: dado un

afo G y dos vértices s y t ¿G tiene un camino de s a t que pase por todos los vértices de G?

ELEMENTARY SP: dado un digrafo pesado G, dos vértices s y t, y un natural k, ¿G tiene un camino que no repite vertices ni aristas de s a t de peso menor o igual a k?

HAMPATH NPC, qvq ESP es NPC

ESP NPC <=>
i) ESP NP
ii) HAMPATH $≤_p$ ESP

#### i) ESP NP (qvq que para toda instancia positiva de ESP, puedo dar un certificado de tamaño polinomial verificable en tiempo polinomial)

* Certificado: Los vértices del camino en un vector

* Verificador:
* Verificar que los vértices del certificado pertenezcan al grafo y que no hay vértices repetidos
* Verificar que cada vértice del certificado tengo un arco en el grafo hacia el siguiente del vector
* Verificar que la suma de los pesos de cada arco del camino sea menos o igual a k

* Es fácil ver que tanto el tamaño del certificado como su verificador son polinomiales

#### ii) QVQ HAMPATH $≤_p$ ESP

> Luego la reducción es bastante clara. Dado un digrafo G=(V, E), para responder si G tiene un camino Hamiltoniano, construí un digrafo pesado G'=(V, E, w), donde w(e) = -1 para todo e en E. Esto es claramente feasible en tiempo polinomial en el tamaño de G.

> Ahora tenés que (G, s, t) en HAMILTONIAN-PATH $<=>$ (G', s, t, k=-(n-1)) en ESP.

> $=>$) Si G tiene un camino Hamiltoniano de s a t, entonces ese camino tiene n - 1 aristas, es simple, y tiene peso exactamente -(n - 1) en G'. Luego G' tiene un camino simple de s a t de peso menor o igual (en particular igual) a k = -(n - 1).

> $<=$) Si G' tiene un camino simple de s a t peso menor o igual a k = -(n - 1), llamémoslo P. G' y G tienen las mismas aristas, luego P existe en G. En G, P tiene n - 1 aristas (porque en G' cada arista tiene peso -1, y no puede tener más de n - 1 aristas porque repetiría vértices), es simple, y va de s a t. Luego tiene que pasar por todos los vértices de G, y luego es un camino Hamiltoniano de s a t.

> [name=flebron] [time=Sat, Feb 5, 2022 9:06 PM] [fuente](https://t.me/c/1461330951/3953)

### 19. El problema DOUBLE-SAT consiste en deteminar si una fórmula proposicional φ tiene al menos dos valuaciones que la satisfacen. Demostrar que DOUBLE-SAT es NP-completo.

Podemos demostralo usando Levin-Cook

#### i) DOUBLE-SAT NP

* Certificado: 2 vectores de (cant de variables) booleanos

* Verifico:
* que ambos vectores sean distintos
* que al asignar las variables la fórmula da verdadero para ambos vectores

* Es fácil ver que tanto el tamaño del certificado como su verificador son polinomiales

#### ii) SAT $≤_p$ DOUBLE-SAT

* Para probar esto, queremos ver que $SAT ∈ Y <=> f(SAT) ∈ Y_{2-SAT}$ (abuso de notación: no son los problemas SAT y 2-SAT, sino instancias de los mismos)

$=>$)

Dada una instancia de SAT verdadera, puedo tomar como f una función que le agregue una disyunción que consista en una tautología construìda con una nueva variable.

Ejemplo: Si la instancia original es: $(x_1 ∨ x_2) ∧ x_3$, podemos construir una instancia $(x_1 ∨ x_2) ∧ x_3 ∧ (y ∨ ¬y)$, la cual va a ser trivialmente verdadera bajo la asignación de variables que teníamos para los 2 valores que puede tomar $y$.

De esta forma, vamos a tener una fórmula lógica con al menos 2 asignaciones posibles de verdad (el caso donde $y$ es positivo y donde es negativo). Por ende la nueva instancia cumple 2-SAT.

$<=$)

Sabemos que tenemos una instancia verdadera de 2-SAT construída agregándole una nueva disyunción a SAT. Podemos quitarle la última disyunción para recuperar la instancia de SAT.

CONSULTAR: vale esto? estamos usando f⁻¹?

Como esta es una fórmula lógica igual o más débil que la que teníamos en 2-SAT, es trivialmnente satisfacible.

### 20. Una biclique B de un grafo G es un conjunto de vértices que induce un subgrafo bipartito completo de G. Dados dos grafos G y H, el grafo G + H se obtiene agregando todas las aristas entre V (G) y V (H) en G ∪ H. Dado un grafo G y un natural k, el problema BICLIQUE consiste en determinar si G tiene una biclique de cardinal mayor o igual a k.

#### a) Demostrar que un grafo G tiene una clique de tamaño k si y solo si $\overline{G} + \overline{G}$ tiene una biclique de tamaño 2k.

#### b) Demostrar que BICLIQUE es NP-completo sabiendo que CLIQUE es NP-completo.

Para ver que BICLIQUE es NPC, podemos usar el teorema de Levin-Cook:

qvq:

* BICLIQUE ∈ NP
* CLIQUE $≤_p$ BICLIQUE

#### i) BICLIQUE NP

Hacemos los 3 pasos de Souli:

* El cert son las 2 particiones de vértices que inducen el subgrafo bipartito completo.

* El verif verifica:
* No-aristas ilegales: Para cada vértice de cada partición, que solo tenga aristas que lo conecten con aristas que no estén en la misma partición.
* Completo: Que cada vértice de cada partición incide con todos los vértices de la otra.

* "es facil ver que tam poli y verif poli"

#### CLIQUE $≤_p$ BICLIQUE

* $I ∈ Y_{CLIQUE} <=> f(I) ∈ Y_{BICLIQUE}$

$I = <G, k> = <<V, E>, k>$

Dada una instancia positiva de clique, a partir de lo demostrado en el punto a), podemos tranformarla en una suma de su complemento consigo mismo. Entonces, tendrá una clique de tamaño 2k.

* Ejemplo con $k = 3$: $K_3^c + K_3^c$:

graph K3c_plus_K3c {

    subgraph cluster_1 {

        2; 1; 3;
    }  

    subgraph cluster_2 {

        4; 6; 5;
    }

    1 -- 4;
    1 -- 5;
    1 -- 6;
    
    2 -- 4;
    2 -- 5;
    2 -- 6;

    3 -- 4;
    3 -- 5;
    3 -- 6;
}