# Final 2022.02.24

* Enunciado:

###### tags: `Finales`

## Resumen

### Glosario/definiciones

* La reducción de Cook-Levin es del problema ya conocido al que queremos demostrar que es NPC

### Trucos

* Si no sale el de dinamica de una, hacer ejemplos chiquitos y ver cómo es el comportamiento

* Dejar el de programación dinámica para la última hora/últimas 2hs (porque te podés pasar todo el examen con la función, si no te sale)

* Resolver primero una versión más fácil del enunciado (por ejemplo, devolver el tamaño de la supersecuencia común más corta, en vez de la supersecuencia en sí)

* En general en un problema de DP, "el mejor valor" vs "la sucesión que te da el mejor valor" es sólo acordarse de qué estados usaste como predecesores en cada estado. Si, por ejemplo, d[i] = min(d[j] + a[j] para j > i), basta con recordar p[i] = j, donde j es el que minimiza d[j] + a[j]. DP siempre es computar algo en un DAG de estados. Si construiste el DAG bien, acordarse el min vs la cadena de predecesores es solo dos líneas mas de código.

* Saber las complejidades de las distintas implementaciones de los algoritmos vistos en clase, por si el ejercicio viene con la complejidad esperada (como en el ejercicio 2).

### Errores comunes

## Resolución

### 1: Dar una funcion recursiva que encuentre la supersecuencia de menor tamaño entre dos secuencias A1 y A2. Una supersecuencia es la secuencia que contiene a todos los elementos de A1 y A2, respetando el orden. Hacer DP de esto y dar la complejidad

https://en.m.wikipedia.org/wiki/Shortest_common_supersequence_problem

#### a) Función

#### b) Algoritmo

* Longitud (más simple): https://www.techiedelight.com/shortest-common-supersequence-introduction-scs-length/

* Supersecuencia (completo): https://www.techiedelight.com/shortest-common-supersequence-finding-scs/

#### c) Complejidad

### 2: Dado un digrafo pesado conexo y dos conjuntos de vertices de $G: S \text{ y } T$ (no necesariamente disjuntos). Diseñar un algoritmo que encuentre el par de vertices $s \in S$ y $t \in T$ tal que la distancia entre estos dos sea la mínima entre todo par de vertices de los conjuntos. Complejidad esperada: $O(|E| log |V|)$. Ayuda: agregar dos vertices ficticios al grafo


Agregamos vértices $s$ y $t$ artificiales, tales que $s$ tiene un arco de peso $0$ hacia todos los vértices de $S$ y todos los vértices de $T$ tienen un arco de peso $0$ hacia $t$.

De esta forma, podemos usar la implementación de Dijkstra con colas de prioridad (que tiene complejidad $O(|E| log |V|)$) modificada para obtener el camino mínimo de $s$ a $t$ (guardando para cada vértice, además de la distancia a $s$, cuál es su predecesor).

Luego, la respuesta será el segundo vértice (perteneciente a $S$) y el anteúltimo (perteneciente a $T$) del camino mínimo (el mismo tendrá la forma $s → s_i → ... → t_j → t$, donde $s_i$ y $t_j$ pueden ser el mismo vértice).

Funciona porque camino mínimo tiene subestructura óptima: puedo tomar un subcamino y también será el mínimo.

### 3: Un ejercicio bastante teorico de flujo. Los que cursaron antes de 2021 tenían un problema de coloreo.


En el punto 3 definían esto pero más resumido y había que:

#### a) Demostrar que $\sum d_v = 0$

#### b) Diseñar un algoritmo que encuentre una circulación máxima válida

### 4: V o F típico de teoría de complejidad computacional

#### 1) Supongamos $P=NP$ entonces todo problema en $NPC$ puede resolverse en tiempo polinomial?

Verdadero:
NPC es un subconjunto de NP (son los problemas que están en NP y en NP-Hard). Entonces si todo problema NP puede resolverse en tiempo polinomial (P=NP), todo problema en NPC también.

#### 2) Supongamos $P=NP$ entonces todo problema en $NP-Hard$ puede resolverse en tiempo polinomial.

Falso

Un problema está en NP-Hard si todo problema NP se puede reducir a él.

Si P = NP, todo problema NP se puede resolver en tiempo polinomial.

Pero los problemas NP-Hard son al menos tan difíciles como todos los NP. Es decir, pueden ser más difíciles computacionalmente de resolver. Por lo que, a priori, no habría garantías de que todo problea NP-hard se pueda resolver en tiempo polinomial.

#### 3) Si $π_1$ pertenece a NP-completo y hay reducción polinomial de $π_1$ a $π_2$ entonces $π_2$ pertenece a $NPC$?

Falso

Si usaramos el teorema de Cook-Levin para demostrar que $π_2$ pertenece a $NPC$, faltaría probar que $π_2$ pertenece a NP.

#### 4) Se sabe que si todo problema que está en $NP$ su problema complemento también está en $NP$. Entonces, ¿$NP = Co-NP$?

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$