From f3f07f72e1d5c6aa9e4482fad63879a6f11b2f52 Mon Sep 17 00:00:00 2001
From: Juan Marin Noguera <juan@mnpi.eu>
Date: Sat, 8 Oct 2022 22:59:52 +0200
Subject: Fin apuntes MC

---
 mc/n7.lyx |  131 ++---
 mc/n8.lyx | 1928 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++-
 2 files changed, 1962 insertions(+), 97 deletions(-)

(limited to 'mc')

diff --git a/mc/n7.lyx b/mc/n7.lyx
index c1791e0..d5dc724 100644
--- a/mc/n7.lyx
+++ b/mc/n7.lyx
@@ -96,27 +96,6 @@ intratable
  solución sea práctica.
 \end_layout
 
-\begin_layout Standard
-Un 
-\series bold
-camino hamiltoniano
-\series default
- en un grafo es un camino que pasa por todos los nodos exactamente una vez.
- Una 
-\series bold
-
-\begin_inset Formula $k$
-\end_inset
-
--clique
-\series default
- es un subgrafo completo de 
-\begin_inset Formula $k$
-\end_inset
-
- nodos.
-\end_layout
-
 \begin_layout Section
 La clase 
 \begin_inset Formula ${\cal P}$
@@ -1276,6 +1255,19 @@ Se añade el nodo
 \end_inset
 
 .
+ Una 
+\series bold
+
+\begin_inset Formula $k$
+\end_inset
+
+-clique
+\series default
+ es un subgrafo completo con 
+\begin_inset Formula $k$
+\end_inset
+
+ nodos.
 \end_layout
 
 \begin_deeper
@@ -1294,6 +1286,43 @@ Si
 \end_layout
 
 \end_deeper
+\begin_layout Enumerate
+\begin_inset Formula $\text{EULCYCLE}\coloneqq\{\langle G\rangle:G\text{ es un grafo dirigido con un ciclo euleriano}\}$
+\end_inset
+
+.
+ Un 
+\series bold
+camino euleriano
+\series default
+ es uno que pasa por todas las aristas exactamente una vez.
+\end_layout
+
+\begin_deeper
+\begin_layout Standard
+Un teorema de Euler dice que un grafo dirigido 
+\begin_inset Formula $G$
+\end_inset
+
+ tiene un ciclo euleriano si y sólo si existe un camino entre cada par de
+ vértices y todos los vértices tienen grado entrante igual a su grado saliente.
+ Ver que hay un camino entre cada par de vértices es polinómico por serlo
+ 
+\begin_inset Formula $\text{PATH}$
+\end_inset
+
+ y el número de pares de vértices, y ver que todos los vértices tienen grado
+ entrante y saliente iguales también.
+\end_layout
+
+\end_deeper
+\begin_layout Enumerate
+\begin_inset Formula $\text{2-COLOR}\coloneqq\{\langle G\rangle:G\text{ es un grafo no dirigido bipartito}\}$
+\end_inset
+
+.
+\end_layout
+
 \begin_layout Enumerate
 Todo 
 \begin_inset Formula $L\in{\cal CF}$
@@ -1693,66 +1722,6 @@ end{samepage}
 
 \end_layout
 
-\begin_layout Standard
-Están en 
-\begin_inset Formula ${\cal NP}$
-\end_inset
-
-:
-\end_layout
-
-\begin_layout Enumerate
-\begin_inset Formula $\text{HAMPATH}\coloneqq\{\langle G,s,t\rangle:G\text{ es un grafo dirigido con camino hamiltoniano de }s\text{ a }t\}$
-\end_inset
-
-.
-\end_layout
-
-\begin_deeper
-\begin_layout Standard
-El verificador recibe el grafo y el camino hamiltoniano, cuyo tamaño es
- claramente polinómico respecto al del grafo.
- Marca los vértices de dicho camino, rechazando si encuentra un vértice
- que ya ha sido marcado.
- Si queda algún vértice sin marcar, rechaza.
- Para cada arco del camino, si el arco no está en el grafo, rechaza.
- Finalmente, acepta si el camino empieza por 
-\begin_inset Formula $s$
-\end_inset
-
- y termina por 
-\begin_inset Formula $t$
-\end_inset
-
- y rechaza en otro caso.
-\end_layout
-
-\end_deeper
-\begin_layout Enumerate
-\begin_inset Formula $\text{CLIQUE}\coloneqq\{\langle G,k\rangle:G\text{ es grafo no dirigido con }k\text{-clique}\}$
-\end_inset
-
-.
-\end_layout
-
-\begin_deeper
-\begin_layout Standard
-El verificador recibe la lista de 
-\begin_inset Formula $k$
-\end_inset
-
- nodos de la clique, de tamaño claramente proporcional al grafo.
- Si tiene algún nodo que no está en el grafo, o más o menos de 
-\begin_inset Formula $k$
-\end_inset
-
- nodos, rechaza.
- Para cada par de nodos en la clique, si el par no es un arco del grafo,
- rechaza.
- En otro caso acepta.
-\end_layout
-
-\end_deeper
 \begin_layout Standard
 Sean 
 \begin_inset Formula $L_{1},L_{2}\in{\cal NP}$
diff --git a/mc/n8.lyx b/mc/n8.lyx
index a70f8e2..c301fba 100644
--- a/mc/n8.lyx
+++ b/mc/n8.lyx
@@ -159,7 +159,7 @@ se polireduce
 
 \begin_layout Standard
 Un lenguaje 
-\begin_inset Formula $L\in{\cal NP}$
+\begin_inset Formula $L$
 \end_inset
 
  es 
@@ -168,9 +168,9 @@ Un lenguaje
 \begin_inset Formula ${\cal NP}$
 \end_inset
 
--completo
+-duro
 \series default
- si cualquier otro lenguaje 
+ si cualquier lenguaje 
 \begin_inset Formula ${\cal NP}$
 \end_inset
 
@@ -178,6 +178,22 @@ Un lenguaje
 \begin_inset Formula $L$
 \end_inset
 
+, y es 
+\series bold
+
+\begin_inset Formula ${\cal NP}$
+\end_inset
+
+-completo
+\series default
+ si es 
+\begin_inset Formula ${\cal NP}$
+\end_inset
+
+-duro y 
+\begin_inset Formula ${\cal NP}$
+\end_inset
+
 .
  
 \begin_inset Formula ${\cal P}={\cal NP}$
@@ -869,14 +885,6 @@ Este teorema lo descubrieron Stephen Cook y Leonid Levin en los 70, siendo
 -completo.
 \end_layout
 
-\begin_layout Section
-Otros lenguajes 
-\begin_inset Formula ${\cal NP}$
-\end_inset
-
--completos
-\end_layout
-
 \begin_layout Standard
 Un 
 \series bold
@@ -925,23 +933,38 @@ Llamando
 \end_inset
 
 -completos.
- También lo son 
-\begin_inset Formula $\text{HAMPATH}$
+ Sin embargo 
+\begin_inset Formula $\text{SAT}_{\text{2-CNF}}$
 \end_inset
 
- y 
-\begin_inset Formula $k\text{-CLIQUE}$
+, el conjunto de fórmulas satisfacibles en forma normal conjuntiva con a
+ lo sumo 2 literales en cada cláusula, está en 
+\begin_inset Formula ${\cal P}$
+\end_inset
+
+.
+\begin_inset Note Comment
+status open
+
+\begin_layout Plain Layout
+Pone que se puede demostrar por reducción a 
+\begin_inset Formula $\text{PATH}$
 \end_inset
 
 .
 \end_layout
 
+\end_inset
+
+
+\end_layout
+
 \begin_layout Standard
 \begin_inset Formula $\text{SAT}_{1}$
 \end_inset
 
 , el conjunto de fórmulas satisfacibles en lógica de primer orden, es indecidibl
-es, y esto es más o menos lo que probaron Alonzo Church y Alan Turing en
+e, y esto es más o menos lo que probaron Alonzo Church y Alan Turing en
  sus 
 \emph on
 \lang english
@@ -957,5 +980,1878 @@ Entscheidungsproblem
  en 1936.
 \end_layout
 
+\begin_layout Section
+Otros lenguajes 
+\begin_inset Formula ${\cal NP}$
+\end_inset
+
+-completos
+\end_layout
+
+\begin_layout Standard
+Son 
+\begin_inset Formula ${\cal NP}$
+\end_inset
+
+-completos:
+\end_layout
+
+\begin_layout Enumerate
+\begin_inset Formula $\text{CLIQUE}\coloneqq\{\langle G,k\rangle:G\text{ es grafo no dirigido con }k\text{-clique}\}$
+\end_inset
+
+.
+\end_layout
+
+\begin_deeper
+\begin_layout Standard
+Primero vemos que está en 
+\begin_inset Formula ${\cal NP}$
+\end_inset
+
+.
+ El verificador recibe la lista de 
+\begin_inset Formula $k$
+\end_inset
+
+ nodos de la clique, de tamaño claramente proporcional al grafo.
+ Si tiene algún nodo que no está en el grafo, o más o menos de 
+\begin_inset Formula $k$
+\end_inset
+
+ nodos, rechaza.
+ Para cada par de nodos en la clique, si el par no es un arco del grafo,
+ rechaza.
+ En otro caso acepta.
+\end_layout
+
+\begin_layout Standard
+Veamos que 
+\begin_inset Formula $\text{SAT}_{\text{3-cnf}}\leq_{\text{p}}\text{CLIQUE}$
+\end_inset
+
+.
+ Dada una fórmula 
+\begin_inset Formula $\Phi$
+\end_inset
+
+, si algún literal de 
+\begin_inset Formula $\Phi$
+\end_inset
+
+ tiene menos de 3 literales, lo completamos repitiendo uno de ellos.
+ Sea la fórmula resultante 
+\begin_inset Formula $(l_{11}\lor l_{12}\lor l_{13})\land\dots\land(l_{k1}\lor l_{k2}\lor l_{k3})$
+\end_inset
+
+, definimos el grafo 
+\begin_inset Formula $G_{\Phi}=(V,E)$
+\end_inset
+
+ como 
+\begin_inset Formula $V\coloneqq\{(i,j)\}_{1\leq i\leq k}^{1\leq j\leq3}$
+\end_inset
+
+ y 
+\begin_inset Formula $E\coloneqq\{\{(a,b),(c,d)\}\}_{1\leq a<c\leq k,1\leq b,d\leq3,l_{ab}\neq\neg l_{cd},\neg l_{ab}\neq l_{cd}}$
+\end_inset
+
+, y 
+\begin_inset Formula $\Phi$
+\end_inset
+
+ es satisfacible si y sólo si 
+\begin_inset Formula $G_{\Phi}$
+\end_inset
+
+ tiene una 
+\begin_inset Formula $k$
+\end_inset
+
+-clique.
+\end_layout
+
+\begin_layout Enumerate
+\begin_inset Argument item:1
+status open
+
+\begin_layout Plain Layout
+\begin_inset Formula $\implies]$
+\end_inset
+
+
+\end_layout
+
+\end_inset
+
+Dada una asignación de valores que hace a 
+\begin_inset Formula $\Phi$
+\end_inset
+
+ verdadera, para 
+\begin_inset Formula $i\in\{1,\dots,k\}$
+\end_inset
+
+, existe al menos un 
+\begin_inset Formula $n_{i}$
+\end_inset
+
+ tal que 
+\begin_inset Formula $l_{in_{i}}$
+\end_inset
+
+ es verdadero, y como obviamente ningún 
+\begin_inset Formula $l_{in_{i}}$
+\end_inset
+
+ es negación de otro, 
+\begin_inset Formula $\{(i,n_{i})\}_{i=1}^{k}$
+\end_inset
+
+ forma una 
+\begin_inset Formula $k$
+\end_inset
+
+-clique.
+\end_layout
+
+\begin_layout Enumerate
+\begin_inset Argument item:1
+status open
+
+\begin_layout Plain Layout
+\begin_inset Formula $\impliedby]$
+\end_inset
+
+
+\end_layout
+
+\end_inset
+
+Como ningún 
+\begin_inset Formula $(i,j)$
+\end_inset
+
+ conecta con un 
+\begin_inset Formula $(i,k)$
+\end_inset
+
+, la 
+\begin_inset Formula $k$
+\end_inset
+
+-clique está formada por elementos correspondientes a literales de cláusulas
+ distintas, sin que uno sea la negación de otro, por lo que es posible construir
+ una asignación de verdad que haga verdaderos a los literales de la 
+\begin_inset Formula $k$
+\end_inset
+
+-clique y por tanto a 
+\begin_inset Formula $\Phi$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+La función de conversión de 
+\begin_inset Formula $\langle\Phi\rangle$
+\end_inset
+
+ a 
+\begin_inset Formula $\langle G_{\Phi},k\rangle$
+\end_inset
+
+ es claramente polinómica.
+\end_layout
+
+\end_deeper
+\begin_layout Enumerate
+\begin_inset Formula $\text{HAMPATH}\coloneqq\{\langle G,s,t\rangle:G\text{ es un grafo dirigido con camino hamiltoniano de }s\text{ a }t\}$
+\end_inset
+
+.
+ Un 
+\series bold
+camino hamiltoniano
+\series default
+ es uno que pasa por todos los vértices exactamente una vez.
+\end_layout
+
+\begin_deeper
+\begin_layout Standard
+Primero vemos que es 
+\begin_inset Formula ${\cal NP}$
+\end_inset
+
+.
+ El verificador recibe el grafo y el camino hamiltoniano, cuyo tamaño es
+ claramente polinómico respecto al del grafo.
+ Marca los vértices de dicho camino, rechazando si encuentra un vértice
+ que ya ha sido marcado.
+ Si queda algún vértice sin marcar, rechaza.
+ Para cada arco del camino, si el arco no está en el grafo, rechaza.
+ Finalmente, acepta si el camino empieza por 
+\begin_inset Formula $s$
+\end_inset
+
+ y termina por 
+\begin_inset Formula $t$
+\end_inset
+
+ y rechaza en otro caso.
+\end_layout
+
+\begin_layout Standard
+Veamos que 
+\begin_inset Formula $\text{SAT}_{\text{3-cnf}}\leq_{\text{p}}\text{HAMPATH}$
+\end_inset
+
+.
+ Sean 
+\begin_inset Formula $\Phi$
+\end_inset
+
+ una fórmula 3-CNF con proposiciones 
+\begin_inset Formula $\{p_{1},\dots,p_{m}\}$
+\end_inset
+
+ distintas y cláusulas 
+\begin_inset Formula $k_{1}\land\dots\land k_{n}$
+\end_inset
+
+, que podemos considerar de 3 elementos cada una.
+ Creamos un grafo dirigido 
+\begin_inset Formula $G_{\Phi}\coloneqq(V,E)$
+\end_inset
+
+, donde
+\begin_inset Formula 
+\begin{align*}
+V\coloneqq & \{a_{i}\}_{i=0}^{m}\cup\{b_{ij}\}_{i\in\{1,\dots,m\}}^{j\in\{1,\dots,3n+3\}}\cup\{c_{j}\}_{j=1}^{n},\\
+E\coloneqq & \{(a_{i-1},b_{i1}),(a_{i-1},b_{i,3n+3}),(b_{i1},a_{i}),(b_{i1},a_{i,3n+3})\}_{i=1}^{m}\cup\\
+ & \cup\{(b_{ij},b_{i,j+1}),(b_{i,j+1},b_{ij})\}_{i\in\{1,\dots,m\}}^{j\in\{1,\dots,3n+2\}}\cup\\
+ & \cup\{(b_{i,3j},c_{j}),(c_{j},b_{i,3j+1})\}_{i\in\{1,\dots m\},j\in\{1,\dots,n\}}^{p_{i}\text{ aparece en }k_{j}}\cup\\
+ & \cup\{(b_{i,3j+1},c_{j}),(c_{j},b_{i,3j})\}_{i\in\{1,\dots,m\},j\in\{1,\dots,n\}}^{\neg p_{1}\text{ aparece en }k_{j}}.
+\end{align*}
+
+\end_inset
+
+
+\begin_inset Formula $\Phi$
+\end_inset
+
+ es satisfacible si y sólo si 
+\begin_inset Formula $G_{\Phi}$
+\end_inset
+
+ tiene un camino hamiltoniano de 
+\begin_inset Formula $a_{0}$
+\end_inset
+
+ a 
+\begin_inset Formula $a_{m}$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Enumerate
+\begin_inset Argument item:1
+status open
+
+\begin_layout Plain Layout
+\begin_inset Formula $\implies]$
+\end_inset
+
+
+\end_layout
+
+\end_inset
+
+Tomamos una asignación de valores que haga verdadera a 
+\begin_inset Formula $\Phi$
+\end_inset
+
+ y, para cada 
+\begin_inset Formula $k_{j}$
+\end_inset
+
+, elegimos un literal en 
+\begin_inset Formula $k_{j}$
+\end_inset
+
+ que tenga valor verdadero.
+ Para construir el camino, primero, para 
+\begin_inset Formula $i$
+\end_inset
+
+ de 1 a 
+\begin_inset Formula $m$
+\end_inset
+
+, si 
+\begin_inset Formula $p_{i}$
+\end_inset
+
+ es verdadero, recorremos 
+\begin_inset Formula $a_{i-1},b_{i1},b_{i2},\dots,b_{i,3n+3},a_{i}$
+\end_inset
+
+, y si es falso, recorremos 
+\begin_inset Formula $a_{i-1},b_{i,3n+3},b_{i,3n+2},\dots,b_{i1},a_{i}$
+\end_inset
+
+.
+ Entonces, para cada 
+\begin_inset Formula $k_{j}$
+\end_inset
+
+, si el literal elegido de 
+\begin_inset Formula $k_{j}$
+\end_inset
+
+ es de la forma 
+\begin_inset Formula $p_{i}$
+\end_inset
+
+, cambiamos el eje 
+\begin_inset Formula $(b_{i,3j},b_{i,3j+1})$
+\end_inset
+
+ del camino por 
+\begin_inset Formula $(b_{i,3j},c_{j}),(c_{j},b_{i,3j+1})$
+\end_inset
+
+, y si es de la forma 
+\begin_inset Formula $\neg p_{i}$
+\end_inset
+
+, cambiamos 
+\begin_inset Formula $(b_{i,3j+1},b_{i,3j})$
+\end_inset
+
+ por 
+\begin_inset Formula $(b_{i,3j+1},c_{j}),(c_{j},b_{i,3j})$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Enumerate
+\begin_inset Argument item:1
+status open
+
+\begin_layout Plain Layout
+\begin_inset Formula $\impliedby]$
+\end_inset
+
+
+\end_layout
+
+\end_inset
+
+Para 
+\begin_inset Formula $i\in\{1,\dots,m\}$
+\end_inset
+
+, el camino debe ir de 
+\begin_inset Formula $a_{i-1}$
+\end_inset
+
+ bien a 
+\begin_inset Formula $b_{i1}$
+\end_inset
+
+ o a 
+\begin_inset Formula $b_{i,3n+3}$
+\end_inset
+
+.
+ En el primer caso le asignamos verdadero a 
+\begin_inset Formula $p_{i}$
+\end_inset
+
+, y en el segundo le asignamos falso.
+ Veamos que esta asignación hace verdadera a 
+\begin_inset Formula $\Phi$
+\end_inset
+
+.
+ Para 
+\begin_inset Formula $j\in\{1,\dots,n\}$
+\end_inset
+
+, si el nodo anterior a 
+\begin_inset Formula $c_{j}$
+\end_inset
+
+ en el camino es de la forma 
+\begin_inset Formula $b_{i,3j}$
+\end_inset
+
+, la queremos ver que el siguiente es 
+\begin_inset Formula $b_{i,3j+1}$
+\end_inset
+
+.
+ No puede ser 
+\begin_inset Formula $b_{i,3j}$
+\end_inset
+
+ porque ya ha aparecido, por lo que bien es 
+\begin_inset Formula $b_{i,3j+1}$
+\end_inset
+
+ o un nodo 
+\begin_inset Formula $b_{p,3j}$
+\end_inset
+
+ o 
+\begin_inset Formula $b_{p,3j+1}$
+\end_inset
+
+ con 
+\begin_inset Formula $p\neq i$
+\end_inset
+
+.
+ Si fuera lo segundo, el nodo anterior a 
+\begin_inset Formula $b_{i,3j+1}$
+\end_inset
+
+ no puede ser 
+\begin_inset Formula $c_{j}$
+\end_inset
+
+ porque este ya es anterior a 
+\begin_inset Formula $b_{p,3j}$
+\end_inset
+
+ o 
+\begin_inset Formula $b_{p,3j+1}$
+\end_inset
+
+, por lo que debe ser 
+\begin_inset Formula $b_{i,3j+2}$
+\end_inset
+
+, pero entonces de los sucesores a 
+\begin_inset Formula $b_{i,3j+1}$
+\end_inset
+
+ (
+\begin_inset Formula $b_{i,3j}$
+\end_inset
+
+, 
+\begin_inset Formula $b_{i,3j+2}$
+\end_inset
+
+ y posiblemente 
+\begin_inset Formula $c_{j}$
+\end_inset
+
+) ninguno puede ser el siguiente a este.
+\begin_inset Formula $\#$
+\end_inset
+
+ Por tanto el siguiente a 
+\begin_inset Formula $c_{j}$
+\end_inset
+
+ en el camino es 
+\begin_inset Formula $b_{i,3j+1}$
+\end_inset
+
+.
+ La otra alternativa es que el nodo anterior a 
+\begin_inset Formula $c_{j}$
+\end_inset
+
+ sea de la forma 
+\begin_inset Formula $b_{i,3j+1}$
+\end_inset
+
+, con lo que el siguiente es 
+\begin_inset Formula $b_{i,3j}$
+\end_inset
+
+ por un argumento análogo.
+ Entonces, para un mismo 
+\begin_inset Formula $i$
+\end_inset
+
+, los 
+\begin_inset Formula $b_{ij}$
+\end_inset
+
+ se recorren con 
+\begin_inset Formula $j$
+\end_inset
+
+ siempre ascendente o siempre descendente.
+ En el primer caso el anterior a 
+\begin_inset Formula $b_{i1}$
+\end_inset
+
+ es 
+\begin_inset Formula $a_{i-1}$
+\end_inset
+
+ y 
+\begin_inset Formula $p_{i}$
+\end_inset
+
+ es verdadero, y como 
+\begin_inset Formula $k_{j}$
+\end_inset
+
+ contiene a 
+\begin_inset Formula $p_{i}$
+\end_inset
+
+ ya que 
+\begin_inset Formula $(b_{i,3j},c_{j})\in E$
+\end_inset
+
+, la asignación hace a 
+\begin_inset Formula $k_{j}$
+\end_inset
+
+ verdadera.
+ En el segundo, el anterior a 
+\begin_inset Formula $b_{i,3n+3}$
+\end_inset
+
+ es 
+\begin_inset Formula $a_{i-1}$
+\end_inset
+
+ y 
+\begin_inset Formula $p_{i}$
+\end_inset
+
+ es falso, y como 
+\begin_inset Formula $k_{j}$
+\end_inset
+
+ contiene a 
+\begin_inset Formula $\neg p_{i}$
+\end_inset
+
+ ya que 
+\begin_inset Formula $(b_{i,3j+1},c_{j})\in E$
+\end_inset
+
+, la asignación hace a 
+\begin_inset Formula $k_{j}$
+\end_inset
+
+ verdadera.
+\end_layout
+
+\begin_layout Standard
+La función de conversión de 
+\begin_inset Formula $\langle\Phi\rangle$
+\end_inset
+
+ a 
+\begin_inset Formula $\langle G_{\Phi},a_{0},a_{m}\rangle$
+\end_inset
+
+ es claramente polinómica.
+\end_layout
+
+\end_deeper
+\begin_layout Enumerate
+\begin_inset Formula $\text{HAMCYCLE}\coloneqq\{\langle G\rangle:G\text{ es un grafo dirigido con un ciclo hamiltoniano}\}$
+\end_inset
+
+.
+\end_layout
+
+\begin_deeper
+\begin_layout Standard
+Claramente es 
+\begin_inset Formula ${\cal NP}$
+\end_inset
+
+, pues basta tomar un nodo 
+\begin_inset Formula $s$
+\end_inset
+
+ de 
+\begin_inset Formula $G$
+\end_inset
+
+ arbitrario y decidir si 
+\begin_inset Formula $\langle G,s,s\rangle\in\text{HAMPATH}$
+\end_inset
+
+.
+ Veamos ahora que 
+\begin_inset Formula $\text{HAMPATH}\leq_{\text{p}}\text{HAMCYCLE}$
+\end_inset
+
+.
+ Sean 
+\begin_inset Formula $G=(V,E)$
+\end_inset
+
+ un grafo dirigido, 
+\begin_inset Formula $a,b\in V$
+\end_inset
+
+ y 
+\begin_inset Formula $G'\coloneqq(V',E')$
+\end_inset
+
+ un grafo dirigido dado por 
+\begin_inset Formula $V'\coloneqq V\sqcup\{a',b'\}$
+\end_inset
+
+ y 
+\begin_inset Formula $E'\coloneqq E\sqcup\{(b,b'),(b',a'),(a',a)\}$
+\end_inset
+
+.
+ Entonces 
+\begin_inset Formula $G$
+\end_inset
+
+ tiene un camino hamiltoniano de 
+\begin_inset Formula $a$
+\end_inset
+
+ a 
+\begin_inset Formula $b$
+\end_inset
+
+ si y sólo si 
+\begin_inset Formula $G'$
+\end_inset
+
+ tiene un ciclo hamiltoniano.
+\end_layout
+
+\begin_layout Enumerate
+\begin_inset Argument item:1
+status open
+
+\begin_layout Plain Layout
+\begin_inset Formula $\implies]$
+\end_inset
+
+
+\end_layout
+
+\end_inset
+
+Concatenamos al camino hamiltoniano de 
+\begin_inset Formula $a$
+\end_inset
+
+ a 
+\begin_inset Formula $b$
+\end_inset
+
+ el camino 
+\begin_inset Formula $bb'a'a$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Enumerate
+\begin_inset Argument item:1
+status open
+
+\begin_layout Plain Layout
+\begin_inset Formula $\impliedby]$
+\end_inset
+
+
+\end_layout
+
+\end_inset
+
+El ciclo hamiltoniano debe contener el subcamino 
+\begin_inset Formula $bb'a'a$
+\end_inset
+
+ por ser esta la única forma que pase por 
+\begin_inset Formula $b'$
+\end_inset
+
+ y 
+\begin_inset Formula $a'$
+\end_inset
+
+.
+ Entonces, tomando el ciclo empezando por 
+\begin_inset Formula $a$
+\end_inset
+
+, este debe acabar por dicho subcamino, y eliminando esta parte nos queda
+ un camino de 
+\begin_inset Formula $a$
+\end_inset
+
+ a 
+\begin_inset Formula $b$
+\end_inset
+
+ que pasa por todos los nodos en 
+\begin_inset Formula $V$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+La función de conversión de 
+\begin_inset Formula $\langle G,a,b\rangle$
+\end_inset
+
+ a 
+\begin_inset Formula $\langle G'\rangle$
+\end_inset
+
+ es claramente polinómica.
+\end_layout
+
+\end_deeper
+\begin_layout Enumerate
+\begin_inset Formula $\text{UHAMCYCLE}\coloneqq\{\langle G\rangle:G\text{ es un grafo no dirigido con un ciclo hamiltoniano}\}$
+\end_inset
+
+.
+\end_layout
+
+\begin_deeper
+\begin_layout Standard
+Claramente es 
+\begin_inset Formula ${\cal NP}$
+\end_inset
+
+, pues equivale a decidir 
+\begin_inset Formula $\text{HAMCYCLE}$
+\end_inset
+
+ sobre un grafo dirigido cuyos nodos son los de 
+\begin_inset Formula $G$
+\end_inset
+
+ y cuyos arcos son 
+\begin_inset Formula $(a,b)$
+\end_inset
+
+ y 
+\begin_inset Formula $(b,a)$
+\end_inset
+
+ para cada eje 
+\begin_inset Formula $\{a,b\}$
+\end_inset
+
+ de 
+\begin_inset Formula $G$
+\end_inset
+
+.
+ Para ver que es 
+\begin_inset Formula ${\cal NP}$
+\end_inset
+
+-completo, vemos que 
+\begin_inset Formula $\text{HAMCYCLE}\leq_{\text{p}}\text{UHAMCYCLE}$
+\end_inset
+
+.
+ Dado un grafo dirigido 
+\begin_inset Formula $G=(V,E)$
+\end_inset
+
+, definimos un grafo no dirigido 
+\begin_inset Formula $G'\coloneqq(V',E')$
+\end_inset
+
+ dado por
+\begin_inset Formula 
+\begin{align*}
+V' & \coloneqq\{(v,0),(v,1),(v,2)\}_{v\in V},\\
+E' & \coloneqq\{\{(v,0),(v,1)\},\{(v,1),(v,2)\}\}_{v\in V}\cup\{\{(u,2),(v,0)\}\}_{(u,v)\in E},
+\end{align*}
+
+\end_inset
+
+ y 
+\begin_inset Formula $G$
+\end_inset
+
+ tiene un ciclo hamiltoniano si y sólo si lo tiene 
+\begin_inset Formula $G'$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Enumerate
+\begin_inset Argument item:1
+status open
+
+\begin_layout Plain Layout
+\begin_inset Formula $\implies]$
+\end_inset
+
+
+\end_layout
+
+\end_inset
+
+Sea 
+\begin_inset Formula $u_{1}\cdots u_{n}u_{1}$
+\end_inset
+
+ un ciclo hamiltoniano en 
+\begin_inset Formula $G$
+\end_inset
+
+,
+\begin_inset Formula 
+\[
+(u_{1},0)(u_{1},1)(u_{1},2)\cdots(u_{n},0)(u_{n},1)(u_{n},2)(u_{1},0)
+\]
+
+\end_inset
+
+ es uno en 
+\begin_inset Formula $G'$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Enumerate
+\begin_inset Argument item:1
+status open
+
+\begin_layout Plain Layout
+\begin_inset Formula $\impliedby]$
+\end_inset
+
+
+\end_layout
+
+\end_inset
+
+Si 
+\begin_inset Formula $V'$
+\end_inset
+
+ es vacío, 
+\begin_inset Formula $V$
+\end_inset
+
+ también y hemos terminado.
+ En otro caso, dado un ciclo hamiltoniano de 
+\begin_inset Formula $G'$
+\end_inset
+
+ y un nodo de este de la forma 
+\begin_inset Formula $(u_{1},1)$
+\end_inset
+
+, podemos suponer que el anterior es 
+\begin_inset Formula $(u_{1},0)$
+\end_inset
+
+ y el siguiente es 
+\begin_inset Formula $(u_{1},2)$
+\end_inset
+
+, pues en otro caso ocurre al revés y damos la vuelta al ciclo.
+ Vemos por inducción que, para 
+\begin_inset Formula $k\in\{1,\dots,n\}$
+\end_inset
+
+, el ciclo contiene un subcamino de la forma 
+\begin_inset Formula $(u_{1},0)(u_{1},1)(u_{1},2)\cdots(u_{k},0)(u_{k},1)(u_{k},2)$
+\end_inset
+
+, pues entonces en particular esto ocurre para 
+\begin_inset Formula $k=n$
+\end_inset
+
+ y 
+\begin_inset Formula $u_{1}\cdots u_{n}u_{1}$
+\end_inset
+
+ es un ciclo hamiltoniano en 
+\begin_inset Formula $G$
+\end_inset
+
+.
+ Para 
+\begin_inset Formula $k=1$
+\end_inset
+
+ ya lo hemos visto.
+ Para 
+\begin_inset Formula $k>1$
+\end_inset
+
+, probado esto para 
+\begin_inset Formula $k-1$
+\end_inset
+
+, por construcción el elemento siguiente a 
+\begin_inset Formula $(u_{k-1},2)$
+\end_inset
+
+ es de la forma 
+\begin_inset Formula $(u_{k},0)$
+\end_inset
+
+.
+ El elemento anterior a 
+\begin_inset Formula $(u_{k},1)$
+\end_inset
+
+ debe ser 
+\begin_inset Formula $(u_{k},0)$
+\end_inset
+
+ ya que de lo contrario sería 
+\begin_inset Formula $(u_{k},2)$
+\end_inset
+
+ y el siguiente sería 
+\begin_inset Formula $(u_{k},0)$
+\end_inset
+
+, pero 
+\begin_inset Formula $(u_{k},0)$
+\end_inset
+
+ ya es el siguiente de 
+\begin_inset Formula $(u_{k-1},2)\#$
+\end_inset
+
+.
+ Por tanto a 
+\begin_inset Formula $(u_{k},0)$
+\end_inset
+
+ le siguen 
+\begin_inset Formula $(u_{k},1)$
+\end_inset
+
+ y 
+\begin_inset Formula $(u_{k},2)$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+Claramente la función de conversión de 
+\begin_inset Formula $\langle G\rangle$
+\end_inset
+
+ a 
+\begin_inset Formula $\langle G'\rangle$
+\end_inset
+
+ es polinómica.
+\end_layout
+
+\end_deeper
+\begin_layout Enumerate
+\begin_inset Formula $\text{COLOR}\coloneqq\{\langle G,k\rangle:G\text{ es un grafo no dirigido }k\text{-coloreable}\}$
+\end_inset
+
+.
+ Un grafo no dirigido 
+\begin_inset Formula $G=(V,E)$
+\end_inset
+
+ es 
+\series bold
+
+\begin_inset Formula $k$
+\end_inset
+
+-coloreable
+\series default
+ si existe una función 
+\begin_inset Formula $f:V\to\{1,\dots,k\}$
+\end_inset
+
+ tal que 
+\begin_inset Formula $f(u)\neq f(v)$
+\end_inset
+
+ para 
+\begin_inset Formula $\{u,v\}\in E$
+\end_inset
+
+, en cuyo caso 
+\begin_inset Formula $f$
+\end_inset
+
+ es un 
+\series bold
+coloreado
+\series default
+ de 
+\begin_inset Formula $G$
+\end_inset
+
+.
+ En particular un grafo es bipartito si es 2-coloreable.
+\begin_inset Note Comment
+status open
+
+\begin_layout Plain Layout
+Para ver que es 
+\begin_inset Formula ${\cal NP}$
+\end_inset
+
+ consideramos un verificador que toma un coloreado potencial de 
+\begin_inset Formula $f$
+\end_inset
+
+; si no colorea algún nodo o lo colorea más de una vez, rechaza; si a algún
+ nodo le da un color mayor que 
+\begin_inset Formula $k$
+\end_inset
+
+, rechaza; para cada arista, si a los dos nodos que conecta les da el mismo
+ color, rechaza; en otro caso acepta.
+ Este verificador es polinómico.
+ Para ver que es 
+\begin_inset Formula ${\cal NP}$
+\end_inset
+
+-completo probamos que 
+\begin_inset Formula $\text{SAT}_{\text{3-CNF}}\leq_{\text{p}}\text{COLOR}$
+\end_inset
+
+.
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Enumerate
+El 
+\series bold
+TSP
+\series default
+ (
+\series bold
+\emph on
+\lang english
+Traveling Salesman Problem
+\series default
+\emph default
+\lang spanish
+) consiste en encontrar el ciclo hamiltoniano de peso mínimo en un grafo
+ no dirigido completo con pesos.
+ La versión de decisión es 
+\begin_inset Formula $\text{TSP-DEC}$
+\end_inset
+
+, formado por los pares 
+\begin_inset Formula $\langle G,k\rangle$
+\end_inset
+
+ donde 
+\begin_inset Formula $G$
+\end_inset
+
+ es un grafo no dirigido completo con pesos en 
+\begin_inset Formula $\mathbb{N}$
+\end_inset
+
+ con un ciclo hamiltoniano de coste no mayor a 
+\begin_inset Formula $k\in\mathbb{N}$
+\end_inset
+
+, y es 
+\begin_inset Formula ${\cal NP}$
+\end_inset
+
+-completo.
+\end_layout
+
+\begin_deeper
+\begin_layout Standard
+\begin_inset Formula $\text{TSP-DEC}\in{\cal NP}$
+\end_inset
+
+, pues basta tomar un nodo cualquiera del grafo y marcarlo, tomar de forma
+ no determinista otro nodo que no esté marcado y marcarlo, y así hasta marcar
+ todos los nodos, formando así un ciclo, sumar el coste de todos los ejes
+ del ciclo, rechazar si la suma es mayor a 
+\begin_inset Formula $k$
+\end_inset
+
+ y aceptar en otro caso.
+ Para ver que es 
+\begin_inset Formula ${\cal NP}$
+\end_inset
+
+-completo vemos que 
+\begin_inset Formula $\text{UHAMCYCLE}\leq_{p}\text{TSP-DEC}$
+\end_inset
+
+.
+ Dado un grafo no dirigido 
+\begin_inset Formula $G=VE$
+\end_inset
+
+, definimos un grafo no dirigido con pesos 
+\begin_inset Formula $G'=(V,E',\omega)$
+\end_inset
+
+ donde 
+\begin_inset Formula $E'$
+\end_inset
+
+ es tal que 
+\begin_inset Formula $(V,E')$
+\end_inset
+
+ es completo y 
+\begin_inset Formula 
+\[
+\omega(e)\coloneqq\begin{cases}
+1, & e\in E;\\
+2, & e\notin E.
+\end{cases}
+\]
+
+\end_inset
+
+Claramente la función de conversión de 
+\begin_inset Formula $\langle G\rangle$
+\end_inset
+
+ a 
+\begin_inset Formula $\langle G',|V|\rangle$
+\end_inset
+
+ es polinómica, y queda ver que 
+\begin_inset Formula $G$
+\end_inset
+
+ tiene un ciclo hamiltoniano si y sólo si 
+\begin_inset Formula $G'$
+\end_inset
+
+ tiene uno con peso no mayor que 
+\begin_inset Formula $|V|$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Enumerate
+\begin_inset Argument item:1
+status open
+
+\begin_layout Plain Layout
+\begin_inset Formula $\implies]$
+\end_inset
+
+
+\end_layout
+
+\end_inset
+
+Tomamos el mismo ciclo, y como sus 
+\begin_inset Formula $|V|$
+\end_inset
+
+ aristas están en 
+\begin_inset Formula $G$
+\end_inset
+
+, su peso es 
+\begin_inset Formula $|V|$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Enumerate
+\begin_inset Argument item:1
+status open
+
+\begin_layout Plain Layout
+\begin_inset Formula $\impliedby]$
+\end_inset
+
+
+\end_layout
+
+\end_inset
+
+Un ciclo hamiltoniano en 
+\begin_inset Formula $G'$
+\end_inset
+
+ tiene 
+\begin_inset Formula $|V|$
+\end_inset
+
+ aristas y su peso es pues 
+\begin_inset Formula $|V|$
+\end_inset
+
+ más el número de aristas en el ciclo fuera de 
+\begin_inset Formula $E$
+\end_inset
+
+, por lo que si el ciclo tiene peso no mayor que 
+\begin_inset Formula $|V|$
+\end_inset
+
+, no puede tener aristas fuera de 
+\begin_inset Formula $E$
+\end_inset
+
+ y por tanto está en 
+\begin_inset Formula $G$
+\end_inset
+
+.
+\end_layout
+
+\end_deeper
+\begin_layout Enumerate
+\begin_inset Formula $\text{SUBSET-SUM}\coloneqq\{\langle S,t\rangle:S\text{ es una lista de naturales con una subsecuencia que suma }t\}.$
+\end_inset
+
+
+\end_layout
+
+\begin_deeper
+\begin_layout Standard
+Está en 
+\begin_inset Formula ${\cal NP}$
+\end_inset
+
+, y un verificador toma una asignación de qué elementos de la lista se toman
+ y cuáles no, suma los que se toman y compara.
+ Para ver que es 
+\begin_inset Formula ${\cal NP}$
+\end_inset
+
+-completo vemos que 
+\begin_inset Formula $\text{SAT}_{\text{3-CNF}}\leq_{\text{p}}\text{SUBSET-SUM}$
+\end_inset
+
+.
+ Dada una fórmula 
+\begin_inset Formula $\Phi$
+\end_inset
+
+ con variables 
+\begin_inset Formula $p_{1},\dots,p_{m}$
+\end_inset
+
+ distintas y cláusulas 
+\begin_inset Formula $k_{1}\land\dots\land k_{n}$
+\end_inset
+
+, que podemos considerar con 3 literales cada una, tomamos la lista 
+\begin_inset Formula $S\coloneqq(y_{0},z_{0},\dots,y_{m-1},z_{m-1},g_{0},h_{0},\dots,g_{n-1},h_{n-1})$
+\end_inset
+
+, donde 
+\begin_inset Formula $y_{i}$
+\end_inset
+
+ es la suma de 
+\begin_inset Formula $10^{n+i}$
+\end_inset
+
+ más 
+\begin_inset Formula $10^{j}$
+\end_inset
+
+ por cada 
+\begin_inset Formula $k_{j}$
+\end_inset
+
+ con el literal 
+\begin_inset Formula $p_{i}$
+\end_inset
+
+, 
+\begin_inset Formula $z_{i}$
+\end_inset
+
+ es la suma de 
+\begin_inset Formula $10^{n+i}$
+\end_inset
+
+ más 
+\begin_inset Formula $10^{j}$
+\end_inset
+
+ por cada 
+\begin_inset Formula $k_{j}$
+\end_inset
+
+ con el literal 
+\begin_inset Formula $\neg p_{i}$
+\end_inset
+
+ y 
+\begin_inset Formula $g_{j}\coloneqq h_{j}\coloneqq10^{j}$
+\end_inset
+
+, y 
+\begin_inset Formula $t\coloneqq\sum_{i=0}^{m-1}10^{n+i}+3\sum_{j=0}^{n-1}10^{j}$
+\end_inset
+
+.
+ Nótese que para cada posición decimal, una suma de elementos de 
+\begin_inset Formula $S$
+\end_inset
+
+ no incluye más de 5 sumandos con ese dígito no nulo, por lo que nunca hay
+ llevadas.
+ Entonces 
+\begin_inset Formula $\Phi$
+\end_inset
+
+ es satisfacible si y sólo si alguna sublista de 
+\begin_inset Formula $S$
+\end_inset
+
+ suma 
+\begin_inset Formula $t$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Enumerate
+\begin_inset Argument item:1
+status open
+
+\begin_layout Plain Layout
+\begin_inset Formula $\implies]$
+\end_inset
+
+
+\end_layout
+
+\end_inset
+
+Dada una asignación de valores de los 
+\begin_inset Formula $p_{i}$
+\end_inset
+
+, tomamos los 
+\begin_inset Formula $y_{i}$
+\end_inset
+
+ con 
+\begin_inset Formula $p_{i}$
+\end_inset
+
+ verdadero y los 
+\begin_inset Formula $z_{i}$
+\end_inset
+
+ con 
+\begin_inset Formula $p_{i}$
+\end_inset
+
+ falso.
+ Entonces las posiciones decimales de 
+\begin_inset Formula $n$
+\end_inset
+
+ a 
+\begin_inset Formula $n+m-1$
+\end_inset
+
+ valen 1, y las posiciones 
+\begin_inset Formula $j\in\{0,\dots,n-1\}$
+\end_inset
+
+ valen de 1 a 3 ya que la cláusula 
+\begin_inset Formula $k_{j}$
+\end_inset
+
+ contiene entre 1 y 3 literales verdaderos que tendrán el dígito correspondiente
+ en 
+\begin_inset Formula $y_{i}$
+\end_inset
+
+ o 
+\begin_inset Formula $z_{i}$
+\end_inset
+
+ a 1.
+ Añadiendo elementos 
+\begin_inset Formula $g_{j}$
+\end_inset
+
+ o 
+\begin_inset Formula $h_{j}$
+\end_inset
+
+ se llega a 
+\begin_inset Formula $t$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Enumerate
+\begin_inset Argument item:1
+status open
+
+\begin_layout Plain Layout
+\begin_inset Formula $\impliedby]$
+\end_inset
+
+
+\end_layout
+
+\end_inset
+
+Para cada 
+\begin_inset Formula $i$
+\end_inset
+
+, exactamente uno de entre 
+\begin_inset Formula $y_{i}$
+\end_inset
+
+ o 
+\begin_inset Formula $z_{i}$
+\end_inset
+
+ se toma, lo que nos da una asignación de valores con 
+\begin_inset Formula $p_{i}$
+\end_inset
+
+ a verdadero si se toma 
+\begin_inset Formula $y_{i}$
+\end_inset
+
+ o a falso si se toma 
+\begin_inset Formula $z_{i}$
+\end_inset
+
+, y queda ver que esta hace a 
+\begin_inset Formula $\Phi$
+\end_inset
+
+ verdadera.
+ Ahora bien, para cada cláusula 
+\begin_inset Formula $k_{j}$
+\end_inset
+
+, el dígito 
+\begin_inset Formula $j$
+\end_inset
+
+ es 3 y se han tomado entre 0 y 2 de 
+\begin_inset Formula $g_{j}$
+\end_inset
+
+ y 
+\begin_inset Formula $h_{j}$
+\end_inset
+
+, por lo que al menos uno de los 
+\begin_inset Formula $y_{i}$
+\end_inset
+
+ y 
+\begin_inset Formula $z_{i}$
+\end_inset
+
+ que se han tomado tiene un 1 en la posición 
+\begin_inset Formula $j$
+\end_inset
+
+.
+ Si lo tiene un 
+\begin_inset Formula $y_{i}$
+\end_inset
+
+, 
+\begin_inset Formula $k_{j}$
+\end_inset
+
+ contiene el literal 
+\begin_inset Formula $p_{i}$
+\end_inset
+
+ al que se ha asignado verdadero, y si lo tiene un 
+\begin_inset Formula $z_{i}$
+\end_inset
+
+, 
+\begin_inset Formula $k_{j}$
+\end_inset
+
+ contiene el literal 
+\begin_inset Formula $\neg p_{i}$
+\end_inset
+
+ habiendo asignado falso a 
+\begin_inset Formula $p_{i}$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+La función de conversión de 
+\begin_inset Formula $\langle\Phi\rangle$
+\end_inset
+
+ a 
+\begin_inset Formula $\langle S,t\rangle$
+\end_inset
+
+ es polinómica.
+ En efecto, la longitud de 
+\begin_inset Formula $t$
+\end_inset
+
+ es como mucho proporcional a la de 
+\begin_inset Formula $\Phi$
+\end_inset
+
+, como lo es la de cada elemento de 
+\begin_inset Formula $S$
+\end_inset
+
+ y la longitud de 
+\begin_inset Formula $S$
+\end_inset
+
+, y las operaciones usadas se calculan en tiempo polinómico salvo la exponenciac
+ión, pero calcular las potencias de 10 corresponde a multiplicar por 10
+ 
+\begin_inset Formula $n+m-1$
+\end_inset
+
+ veces, pudiendo hacer cada multiplicación en tiempo proporcional a la longitud
+ de los factores, la cual es como mucho proporcional a 
+\begin_inset Formula $n+m-1$
+\end_inset
+
+.
+\end_layout
+
+\end_deeper
+\begin_layout Enumerate
+\begin_inset Formula $\text{VERTEX-COVER}\coloneqq\{\langle G,k\rangle:G\text{ es un grafo no dirigido con una }k\text{-cobertura}\}$
+\end_inset
+
+.
+ Una 
+\series bold
+
+\begin_inset Formula $k$
+\end_inset
+
+-cobertura
+\series default
+ de un grafo no dirigido es un conjunto de 
+\begin_inset Formula $k$
+\end_inset
+
+ nodos tales que toda arista contiene uno de esos nodos.
+\end_layout
+
+\begin_deeper
+\begin_layout Standard
+Para ver que es 
+\begin_inset Formula ${\cal NP}$
+\end_inset
+
+: si 
+\begin_inset Formula $G$
+\end_inset
+
+ tiene menos de 
+\begin_inset Formula $k$
+\end_inset
+
+ nodos, rechaza; se eligen 
+\begin_inset Formula $k$
+\end_inset
+
+ nodos de forma no determinista y, si alguna arista no contiene un nodo
+ de los seleccionados, rechaza; en otro caso acepta.
+ Ahora vemos que 
+\begin_inset Formula $\text{SAT}_{\text{3-CNF}}\leq_{\text{p}}\text{VERTEX-COVER}$
+\end_inset
+
+.
+ Dada una fórmula 3-CNF 
+\begin_inset Formula $\Phi$
+\end_inset
+
+ con variables 
+\begin_inset Formula $p_{1},\dots,p_{m}$
+\end_inset
+
+ distintas y cláusulas 
+\begin_inset Formula $(l_{11}\land l_{12}\land l_{13})\land\dots\land(l_{n1}\land l_{n2}\land l_{n3})$
+\end_inset
+
+, definimos un grafo no dirigido 
+\begin_inset Formula $G_{\Phi}\coloneqq(V,E)$
+\end_inset
+
+ con
+\begin_inset Formula 
+\begin{align*}
+V:= & \{y_{i},z_{i}\}_{i=1}^{m}\cup\{a_{j1},a_{j2},a_{j3}\}_{j=1}^{n},\\
+E:= & \{\{y_{i},z_{i}\}\}_{i=1}^{m}\cup\{\{a_{j1},a_{j2}\},\{a_{j2},a_{j3}\},\{a_{j3},a_{j1}\}\}_{j=1}^{n}\cup\\
+ & \cup\{\{a_{jk},y_{i}\}\}_{l_{jk}=p_{i}}\cup\{\{a_{jk},z_{i}\}\}_{l_{jk}=\neg p_{i}}.
+\end{align*}
+
+\end_inset
+
+
+\begin_inset Formula $\Phi$
+\end_inset
+
+ es satisfacible si y sólo si 
+\begin_inset Formula $G$
+\end_inset
+
+ tiene una 
+\begin_inset Formula $(m+2n)$
+\end_inset
+
+-cobertura.
+\end_layout
+
+\begin_layout Enumerate
+\begin_inset Argument item:1
+status open
+
+\begin_layout Plain Layout
+\begin_inset Formula $\implies]$
+\end_inset
+
+
+\end_layout
+
+\end_inset
+
+Dada una asignación de valores que hace a 
+\begin_inset Formula $\Phi$
+\end_inset
+
+ verdadera, la cobertura está formada por los 
+\begin_inset Formula $y_{i}$
+\end_inset
+
+ con 
+\begin_inset Formula $p_{i}$
+\end_inset
+
+ verdadero, los 
+\begin_inset Formula $z_{i}$
+\end_inset
+
+ con 
+\begin_inset Formula $p_{i}$
+\end_inset
+
+ falso y, para 
+\begin_inset Formula $j\in\{1,\dots,n\}$
+\end_inset
+
+, los 
+\begin_inset Formula $a_{jk}$
+\end_inset
+
+ salvo uno con el correspondiente 
+\begin_inset Formula $l_{jk}$
+\end_inset
+
+ verdadero.
+ Las aristas 
+\begin_inset Formula $\{y_{i},z_{i}\}$
+\end_inset
+
+ y las 
+\begin_inset Formula $\{a_{jp},a_{jq}\}$
+\end_inset
+
+ quedan claramente cubiertas, y las de la forma 
+\begin_inset Formula $\{a_{jk},y_{i}\}$
+\end_inset
+
+ o 
+\begin_inset Formula $\{a_{jk},z_{i}\}$
+\end_inset
+
+ quedan cubiertas por 
+\begin_inset Formula $a_{jk}$
+\end_inset
+
+ si este está en la cobertura o por el otro nodo si no lo está, pues en
+ tal caso 
+\begin_inset Formula $l_{jk}$
+\end_inset
+
+ es verdadero y, si 
+\begin_inset Formula $l_{jk}=p_{i}$
+\end_inset
+
+, el otro nodo es 
+\begin_inset Formula $y_{i}$
+\end_inset
+
+ que está seleccionado, y si 
+\begin_inset Formula $l_{jk}=\neg p_{i}$
+\end_inset
+
+ el otro nodo es 
+\begin_inset Formula $z_{i}$
+\end_inset
+
+ que está seleccionado.
+\end_layout
+
+\begin_layout Enumerate
+\begin_inset Argument item:1
+status open
+
+\begin_layout Plain Layout
+\begin_inset Formula $\impliedby]$
+\end_inset
+
+
+\end_layout
+
+\end_inset
+
+Para 
+\begin_inset Formula $i\in\{1,\dots,m\}$
+\end_inset
+
+ la cobertura debe tener a 
+\begin_inset Formula $y_{i}$
+\end_inset
+
+ o a 
+\begin_inset Formula $z_{i}$
+\end_inset
+
+ para cubrir 
+\begin_inset Formula $\{y_{i},z_{i}\}$
+\end_inset
+
+, y para 
+\begin_inset Formula $j\in\{1,\dots,n\}$
+\end_inset
+
+ debe tener dos de los 
+\begin_inset Formula $a_{jk}$
+\end_inset
+
+ para cubrir todos los 
+\begin_inset Formula $\{a_{jp},a_{jq}\}$
+\end_inset
+
+.
+ Ya llevamos 
+\begin_inset Formula $m+2n$
+\end_inset
+
+ nodos, por lo que no se cubren más.
+ Tomamos la asignación de valores con 
+\begin_inset Formula $p_{i}$
+\end_inset
+
+ a verdadero si la cobertura contiene a 
+\begin_inset Formula $y_{i}$
+\end_inset
+
+ o a falso si contiene a 
+\begin_inset Formula $z_{i}$
+\end_inset
+
+, y entonces 
+\begin_inset Formula $\Phi$
+\end_inset
+
+ es verdadera porque, para cada 
+\begin_inset Formula $j\in\{1,\dots,n\}$
+\end_inset
+
+, hay un 
+\begin_inset Formula $a_{jk}$
+\end_inset
+
+ fuera de la cobertura, de modo que si 
+\begin_inset Formula $\{a_{jk},y_{i}\}\in E$
+\end_inset
+
+ este está cubierto por 
+\begin_inset Formula $y_{i}$
+\end_inset
+
+ y 
+\begin_inset Formula $p_{i}=l_{jk}$
+\end_inset
+
+ es verdadero, y si 
+\begin_inset Formula $\{a_{jk},z_{i}\}\in E$
+\end_inset
+
+ este está cubierto por 
+\begin_inset Formula $z_{i}$
+\end_inset
+
+ y 
+\begin_inset Formula $\neg p_{i}=l_{jk}$
+\end_inset
+
+ es verdadero, y en cualquier caso la 
+\begin_inset Formula $j$
+\end_inset
+
+-ésima cláusula contiene un literal verdadero.
+\end_layout
+
+\begin_layout Standard
+La función de conversión de 
+\begin_inset Formula $\langle\Phi\rangle$
+\end_inset
+
+ a 
+\begin_inset Formula $\langle G_{\Phi},m+2n\rangle$
+\end_inset
+
+ es claramente polinómica.
+\end_layout
+
+\end_deeper
 \end_body
 \end_document
-- 
cgit v1.2.3