3 files changed, 1022 insertions, 2 deletions
diff --git a/mc/n.lyx b/mc/n.lyx
index 86ee807..1f18ae2 100644
--- a/mc/n.lyx
+++ b/mc/n.lyx
@@ -357,5 +357,23 @@ filename "n7.lyx"
 
 \end_layout
 
+\begin_layout Chapter
+Problemas 
+\begin_inset Formula ${\cal NP}$
+\end_inset
+
+-completos
+\end_layout
+
+\begin_layout Standard
+\begin_inset CommandInset include
+LatexCommand input
+filename "n8.lyx"
+
+\end_inset
+
+
+\end_layout
+
 \end_body
 \end_document
diff --git a/mc/n7.lyx b/mc/n7.lyx
index 9bfe853..c1791e0 100644
--- a/mc/n7.lyx
+++ b/mc/n7.lyx
@@ -155,6 +155,47 @@ Los problemas en esta clase se consideran tratables, y el resto intratables.
 \end_layout
 
 \begin_layout Standard
+Una 
+\begin_inset Formula $\text{MT}$
+\end_inset
+
+ 
+\series bold
+computa
+\series default
+ una función 
+\begin_inset Formula $f:D\subseteq\Sigma^{*}\to\Sigma^{*}$
+\end_inset
+
+ si decide 
+\begin_inset Formula $D$
+\end_inset
+
+ y, para 
+\begin_inset Formula $w\in D$
+\end_inset
+
+, termina conteniendo solo 
+\begin_inset Formula $f(w)$
+\end_inset
+
+ en su cinta.
+ Una 
+\series bold
+función polinómica
+\series default
+ o 
+\series bold
+computable en tiempo polinómico
+\series default
+ es una que una 
+\begin_inset Formula $\text{MT}$
+\end_inset
+
+ puede computar con complejidad en tiempo polinómica.
+\end_layout
+
+\begin_layout Standard
 \begin_inset Formula ${\cal P}$
 \end_inset
 
@@ -178,8 +219,8 @@ Una representación es
 \series bold
 razonable
 \series default
- si permite codificar y decodificar objetos hacia una representación interna
- en tiempo polinómico.
+ si existe una función polinómica con inversa polinómica para codificar
+ objetos hacia una representación interna.
 \begin_inset Foot
 status open
 
diff --git a/mc/n8.lyx b/mc/n8.lyx
new file mode 100644
index 0000000..a70f8e2
--- /dev/null
+++ b/mc/n8.lyx
@@ -0,0 +1,961 @@
+#LyX 2.3 created this file. For more info see http://www.lyx.org/
+\lyxformat 544
+\begin_document
+\begin_header
+\save_transient_properties true
+\origin unavailable
+\textclass book
+\begin_preamble
+\input{../defs}
+\end_preamble
+\use_default_options true
+\begin_modules
+algorithm2e
+\end_modules
+\maintain_unincluded_children false
+\language spanish
+\language_package default
+\inputencoding auto
+\fontencoding global
+\font_roman "default" "default"
+\font_sans "default" "default"
+\font_typewriter "default" "default"
+\font_math "auto" "auto"
+\font_default_family default
+\use_non_tex_fonts false
+\font_sc false
+\font_osf false
+\font_sf_scale 100 100
+\font_tt_scale 100 100
+\use_microtype false
+\use_dash_ligatures true
+\graphics default
+\default_output_format default
+\output_sync 0
+\bibtex_command default
+\index_command default
+\paperfontsize default
+\spacing single
+\use_hyperref false
+\papersize default
+\use_geometry false
+\use_package amsmath 1
+\use_package amssymb 1
+\use_package cancel 1
+\use_package esint 1
+\use_package mathdots 1
+\use_package mathtools 1
+\use_package mhchem 1
+\use_package stackrel 1
+\use_package stmaryrd 1
+\use_package undertilde 1
+\cite_engine basic
+\cite_engine_type default
+\biblio_style plain
+\use_bibtopic false
+\use_indices false
+\paperorientation portrait
+\suppress_date false
+\justification true
+\use_refstyle 1
+\use_minted 0
+\index Index
+\shortcut idx
+\color #008000
+\end_index
+\secnumdepth 3
+\tocdepth 3
+\paragraph_separation indent
+\paragraph_indentation default
+\is_math_indent 0
+\math_numbering_side default
+\quotes_style french
+\dynamic_quotes 0
+\papercolumns 1
+\papersides 1
+\paperpagestyle default
+\tracking_changes false
+\output_changes false
+\html_math_output 0
+\html_css_as_file 0
+\html_be_strict false
+\end_header
+
+\begin_body
+
+\begin_layout Standard
+Una 
+\series bold
+reducción de tiempo polinómico
+\series default
+ de un lenguaje 
+\begin_inset Formula $L$
+\end_inset
+
+ a otro 
+\begin_inset Formula $L'$
+\end_inset
+
+ es una función polinómica 
+\begin_inset Formula $f:\Sigma^{*}\to\Sigma^{*}$
+\end_inset
+
+ tal que, para 
+\begin_inset Formula $w\in\Sigma^{*}$
+\end_inset
+
+, 
+\begin_inset Formula $w\in L\iff f(w)\in L'$
+\end_inset
+
+.
+ Si existe decimos que 
+\begin_inset Formula $L$
+\end_inset
+
+ 
+\series bold
+se puede reducir polinómicamente
+\series default
+ o 
+\series bold
+se polireduce
+\series default
+ a 
+\begin_inset Formula $L'$
+\end_inset
+
+, 
+\begin_inset Formula $L\leq_{\text{p}}L'$
+\end_inset
+
+.
+ Claramente si 
+\begin_inset Formula $L\leq_{\text{p}}L'$
+\end_inset
+
+ y 
+\begin_inset Formula $L'\in{\cal P}$
+\end_inset
+
+ entonces 
+\begin_inset Formula $L\in{\cal P}$
+\end_inset
+
+, y si 
+\begin_inset Formula $L\leq_{\text{p}}L'$
+\end_inset
+
+ y 
+\begin_inset Formula $L'\in{\cal NP}$
+\end_inset
+
+ entonces 
+\begin_inset Formula $L\in{\cal NP}$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+Un lenguaje 
+\begin_inset Formula $L\in{\cal NP}$
+\end_inset
+
+ es 
+\series bold
+
+\begin_inset Formula ${\cal NP}$
+\end_inset
+
+-completo
+\series default
+ si cualquier otro lenguaje 
+\begin_inset Formula ${\cal NP}$
+\end_inset
+
+ se polireduce a 
+\begin_inset Formula $L$
+\end_inset
+
+.
+ 
+\begin_inset Formula ${\cal P}={\cal NP}$
+\end_inset
+
+ si y sólo si algún lenguaje 
+\begin_inset Formula ${\cal NP}$
+\end_inset
+
+-completo está en 
+\begin_inset Formula ${\cal P}$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Itemize
+\begin_inset Argument item:1
+status open
+
+\begin_layout Plain Layout
+\begin_inset Formula $\implies]$
+\end_inset
+
+
+\end_layout
+
+\end_inset
+
+Obvio.
+\end_layout
+
+\begin_layout Itemize
+\begin_inset Argument item:1
+status open
+
+\begin_layout Plain Layout
+\begin_inset Formula $\impliedby]$
+\end_inset
+
+
+\end_layout
+
+\end_inset
+
+En tal caso todo lenguaje en 
+\begin_inset Formula ${\cal NP}$
+\end_inset
+
+ se polireduce a él y por tanto también está en 
+\begin_inset Formula ${\cal P}$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+
+\series bold
+Tercer teorema de reducibilidad:
+\series default
+ Si 
+\begin_inset Formula $L\leq_{\text{p}}L'$
+\end_inset
+
+ y 
+\begin_inset Formula $L$
+\end_inset
+
+ es 
+\begin_inset Formula ${\cal NP}$
+\end_inset
+
+-completo entonces 
+\begin_inset Formula $L'$
+\end_inset
+
+ es 
+\begin_inset Formula ${\cal NP}$
+\end_inset
+
+-completo.
+\end_layout
+
+\begin_layout Section
+El problema SAT
+\end_layout
+
+\begin_layout Standard
+Una 
+\series bold
+proposición
+\series default
+ o 
+\series bold
+fórmula booleana
+\series default
+ es una 
+\series bold
+variable
+\series default
+ o 
+\series bold
+proposición atómica
+\series default
+ dada por una secuencia de letras, una 
+\series bold
+conjunción
+\series default
+ 
+\begin_inset Formula $(a\land b)$
+\end_inset
+
+, una 
+\series bold
+disyunción
+\series default
+ 
+\begin_inset Formula $(a\lor b)$
+\end_inset
+
+ o una 
+\series bold
+negación
+\series default
+ 
+\begin_inset Formula $(\neg a)$
+\end_inset
+
+, donde 
+\begin_inset Formula $a$
+\end_inset
+
+ y 
+\begin_inset Formula $b$
+\end_inset
+
+ son proposiciones.
+ Podemos reducir la cantidad de paréntesis entendiendo que la negación tiene
+ precedencia sobre la disyunción y la conjunción y que estas son asociativas
+ por la izquierda.
+\end_layout
+
+\begin_layout Standard
+Una 
+\series bold
+asignación de valores
+\series default
+ es una función que a cada variable de una cierta proposición le asigna
+ un 
+\series bold
+valor de verdad
+\series default
+, 
+\begin_inset Quotes cld
+\end_inset
+
+verdadero
+\begin_inset Quotes crd
+\end_inset
+
+ o 
+\begin_inset Quotes cld
+\end_inset
+
+falso
+\begin_inset Quotes crd
+\end_inset
+
+.
+ Dada una asignación de valores, el valor de verdad de 
+\begin_inset Formula $(a\land b)$
+\end_inset
+
+ es verdadero si lo es el de 
+\begin_inset Formula $a$
+\end_inset
+
+ y el de 
+\begin_inset Formula $b$
+\end_inset
+
+ y falso en otro caso; el de 
+\begin_inset Formula $(a\lor b)$
+\end_inset
+
+ es falso si lo es el de 
+\begin_inset Formula $a$
+\end_inset
+
+ y el de 
+\begin_inset Formula $b$
+\end_inset
+
+ y verdadero en otro caso, y el de 
+\begin_inset Formula $(\neg a)$
+\end_inset
+
+ es verdadero si y sólo si el de 
+\begin_inset Formula $a$
+\end_inset
+
+ es falso, usando siempre la misma asignación.
+\end_layout
+
+\begin_layout Standard
+Una proposición es 
+\series bold
+satisfacible
+\series default
+ si existe una asignación de valores que le asigna el valor de verdad verdadero.
+ Definimos
+\begin_inset Formula 
+\[
+\text{SAT}\coloneqq\text{SAT}_{0}\coloneqq\text{SAT}_{\text{LP}}\coloneqq\{\langle\Phi\rangle:\Phi\text{ es una fórmula booleana satisfacible}\}.
+\]
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+Sea 
+\begin_inset Formula $N=(Q,\Sigma,\Gamma,\delta,q_{0},q_{\text{f}})$
+\end_inset
+
+ una 
+\begin_inset Formula $\text{MNTD}$
+\end_inset
+
+ en tiempo polinómico, sean 
+\begin_inset Formula $m,c,k\in\mathbb{N}^{*}$
+\end_inset
+
+ tales que, para una entrada de tamaño 
+\begin_inset Formula $n$
+\end_inset
+
+, 
+\begin_inset Formula $N$
+\end_inset
+
+ se ejecuta en no más de 
+\begin_inset Formula $t(n)\coloneqq\max\{m,cn^{k}\}$
+\end_inset
+
+ pasos, un 
+\series bold
+tablón de cálculo
+\series default
+ para 
+\begin_inset Formula $N$
+\end_inset
+
+ es una matriz en 
+\begin_inset Formula ${\cal M}_{t(n)+1}(Q\sqcup\Gamma)$
+\end_inset
+
+ en que cada fila es una configuración de 
+\begin_inset Formula $N$
+\end_inset
+
+ que se sigue de la anterior, siendo la primera una configuración inicial.
+ Las configuraciones se representan como las primeras 
+\begin_inset Formula $t(n)$
+\end_inset
+
+ posiciones de la cinta con el estado de la máquina justo a la izquierda
+ de la posición donde está el cursor.
+\end_layout
+
+\begin_layout Standard
+Para 
+\begin_inset Formula $i\in\{1,\dots,t(n)\}$
+\end_inset
+
+ y 
+\begin_inset Formula $j\in\{1,\dots,t(n)+1\}$
+\end_inset
+
+, la 
+\series bold
+ventana 
+\begin_inset Formula $(i,j)$
+\end_inset
+
+
+\series default
+ de un tablón 
+\begin_inset Formula $(a_{ij})$
+\end_inset
+
+ es la submatriz 
+\begin_inset Formula $2\times3$
+\end_inset
+
+ 
+\begin_inset Formula $(a_{pq})_{i\leq p\leq i+1}^{j-1\leq q\leq j+1}$
+\end_inset
+
+, donde 
+\begin_inset Formula $a_{p0}\coloneqq a_{p,t(n)+1}\coloneqq\#\notin Q\sqcup\Gamma$
+\end_inset
+
+.
+ Una 
+\series bold
+ventana legal
+\series default
+ es una matriz en 
+\begin_inset Formula ${\cal M}_{2\times3}(Q\sqcup\Gamma\sqcup\{\#\})$
+\end_inset
+
+ que puede ser ventana de un tablón de cálculo de 
+\begin_inset Formula $N$
+\end_inset
+
+ sin restringirlo a que la primera fila sea una configuración inicial.
+\end_layout
+
+\begin_layout Standard
+
+\series bold
+Teorema de Cook-Levin:
+\series default
+ 
+\begin_inset Formula $\text{SAT}$
+\end_inset
+
+ es 
+\begin_inset Formula ${\cal NP}$
+\end_inset
+
+-completo.
+ 
+\series bold
+Demostración:
+\series default
+ 
+\begin_inset Formula $\text{SAT}\in{\cal NP}$
+\end_inset
+
+, pues su número de variables es menor que la longitud y por tanto decidir
+ una asignación de forma no determinista tiene tiempo polinómico, y el número
+ de evaluaciones a realizar para determinar el valor de verdad es una por
+ cada símbolo u operador y cada una se hace tiempo polinómico.
+ Sea ahora 
+\begin_inset Formula $A\in{\cal NP}$
+\end_inset
+
+, y queremos ver que 
+\begin_inset Formula $A\leq_{\text{p}}\text{SAT}$
+\end_inset
+
+.
+ Sea 
+\begin_inset Formula $N=(Q,\Sigma,\Gamma,\delta,q_{0},q_{\text{f}})$
+\end_inset
+
+ una 
+\begin_inset Formula $\text{MTND}$
+\end_inset
+
+ que decide 
+\begin_inset Formula $A$
+\end_inset
+
+ en tiempo polinómico, para 
+\begin_inset Formula $w\in\Sigma^{*}$
+\end_inset
+
+, si 
+\begin_inset Formula $N$
+\end_inset
+
+ tiene un tablón con entrada 
+\begin_inset Formula $w$
+\end_inset
+
+ que contiene 
+\begin_inset Formula $q_{\text{f}}$
+\end_inset
+
+ entonces 
+\begin_inset Formula $w=w_{1}\cdots w_{n}\in A$
+\end_inset
+
+, y el recíproco se cumple siempre que después de 
+\begin_inset Formula $q_{\text{f}}$
+\end_inset
+
+ se puede seguir hasta completar las 
+\begin_inset Formula $t(n)$
+\end_inset
+
+ derivaciones, lo que podemos modelar con una transición adicional 
+\begin_inset Formula $(q_{\text{f}},a,\text{R})\in\delta(q_{\text{f}},a)$
+\end_inset
+
+ para cada 
+\begin_inset Formula $a\in\Gamma$
+\end_inset
+
+.
+ Entonces basta encontrar una fórmula booleana computable en tiempo polinómico
+ respecto a 
+\begin_inset Formula $n$
+\end_inset
+
+ cuya satisfacibilidad equivalga a la existencia de un tablón de 
+\begin_inset Formula $N$
+\end_inset
+
+ con entrada 
+\begin_inset Formula $w$
+\end_inset
+
+ que contenga a 
+\begin_inset Formula $q_{\text{f}}$
+\end_inset
+
+.
+ Si 
+\begin_inset Formula $C\coloneqq Q\sqcup\Gamma$
+\end_inset
+
+, la fórmula tendrá 
+\begin_inset Formula $t(n)^{2}|C|$
+\end_inset
+
+ variables 
+\begin_inset Formula $\{x_{ijs}\}_{1\leq i,j\leq t(n)}^{s\in C}$
+\end_inset
+
+, donde 
+\begin_inset Formula $x_{ijs}$
+\end_inset
+
+ indica que el tablón contiene 
+\begin_inset Formula $s$
+\end_inset
+
+ en la posición 
+\begin_inset Formula $(i,j)$
+\end_inset
+
+.
+ Queremos que la primera fila contenga la entrada,
+\begin_inset Formula 
+\[
+\Phi_{\text{start}}\coloneqq x_{11q_{0}}\land x_{12w_{1}}\land x_{13w_{2}}\land\dots\land x_{1,n+1,w_{n}}\land x_{1,n+2,\text{B}}\land\dots\land x_{1,t(n)+1,\text{B}}.
+\]
+
+\end_inset
+
+Tiene que aparecer 
+\begin_inset Formula $q_{\text{f}}$
+\end_inset
+
+,
+\begin_inset Formula 
+\[
+\Phi_{\text{accept}}\coloneqq\bigvee_{1\leq i,j\leq t(n)+1}x_{ijq_{\text{f}}}.
+\]
+
+\end_inset
+
+Cada celda debe contener uno y solo un valor,
+\begin_inset Formula 
+\[
+\Phi_{\text{cell}}=\bigwedge_{1\leq i,j\leq t(n)+1}\left(\bigvee_{s\in C}x_{ijs}\land\bigwedge_{\begin{subarray}{c}
+s,t\in C\\
+s\neq t
+\end{subarray}}(\neg x_{ijs}\lor\neg x_{ijt})\right).
+\]
+
+\end_inset
+
+Finalmente queremos ver que, si una fila es una configuración válida, la
+ siguiente también lo es y se sigue de ella.
+ Si esto es así, todas las ventanas entre las dos filas serán legales.
+ Ahora bien, las ventanas legales son las que tienen las siguientes formas,
+ donde 
+\begin_inset Formula $a,b,c,d\in\Gamma$
+\end_inset
+
+, 
+\begin_inset Formula $e\in\Gamma\sqcup\{\#\}$
+\end_inset
+
+ y 
+\begin_inset Formula ${\bf q},{\bf r}\in Q$
+\end_inset
+
+:
+\begin_inset Formula 
+\begin{align*}
+ & \begin{bmatrix}a & b & c\\
+a & b & c
+\end{bmatrix}, &  & \begin{bmatrix}\# & b & c\\
+\# & b & c
+\end{bmatrix}, &  & \begin{bmatrix}a & b & \#\\
+a & b & \#
+\end{bmatrix};\\
+ & \begin{bmatrix}a & c & e\\
+{\bf r} & c & e
+\end{bmatrix}, &  & \begin{bmatrix}{\bf q} & a & e\\
+b & {\bf r} & e
+\end{bmatrix}, &  & \begin{bmatrix}e & {\bf q} & a\\
+e & b & {\bf r}
+\end{bmatrix}, &  & \begin{bmatrix}e & c & {\bf q}\\
+e & c & b
+\end{bmatrix}, & ({\bf r},b,\text{R}) & \in\delta({\bf q},a);\\
+ & \begin{bmatrix}{\bf q} & a & e\\
+c & b & e
+\end{bmatrix}, &  & \begin{bmatrix}c & {\bf q} & a\\
+{\bf r} & c & b
+\end{bmatrix}, &  & \begin{bmatrix}e & c & {\bf q}\\
+e & {\bf r} & c
+\end{bmatrix}, &  & \begin{bmatrix}e & c & d\\
+e & c & {\bf r}
+\end{bmatrix}, & ({\bf r},b,\text{L}) & \in\delta({\bf q},a).
+\end{align*}
+
+\end_inset
+
+Con esto es claro que, si todas las ventanas entre dos filas son legales,
+ los 
+\begin_inset Quotes cld
+\end_inset
+
+
+\begin_inset Formula $\#$
+\end_inset
+
+
+\begin_inset Quotes crd
+\end_inset
+
+ a los lados se conservan y, si una fila tiene un único estado, la siguiente
+ tendrá uno único que estará a la izquierda o a la derecha, la transición
+ estará en 
+\begin_inset Formula $\delta$
+\end_inset
+
+ y los símbolos que no participan de la transición quedarán igual.
+ Como hay un número finito de ventanas legales y estas solo dependen de
+ 
+\begin_inset Formula $N$
+\end_inset
+
+, la fórmula que buscamos es
+\begin_inset Formula 
+\[
+\Phi_{\text{move}}\coloneqq\bigwedge_{\begin{subarray}{c}
+1\leq i\leq t(n)\\
+1\leq j\leq t(n)+1
+\end{subarray}}\left(\bigvee_{{\footnotesize\begin{bmatrix}a & b & c\\
+d & e & f
+\end{bmatrix}}\text{ventana legal}}\begin{pmatrix}x_{i,j-1,a}\land x_{ijb}\land x_{i,j+1,c}\land\hfill\\
+\land x_{i+1,j-1,d}\land x_{i+1,j,e}\land x_{i+1,j+1,f}
+\end{pmatrix}\right),
+\]
+
+\end_inset
+
+eliminando de la conjunción interior las variables 
+\begin_inset Formula $x_{i0\#}$
+\end_inset
+
+ o 
+\begin_inset Formula $x_{i,t(n)+2,\#}$
+\end_inset
+
+ (que no están definidas y siempre son ciertas) y de la disyunción las ventanas
+ para las que hay 
+\begin_inset Formula $x_{i0s}$
+\end_inset
+
+ o 
+\begin_inset Formula $x_{i,t(n)+2,s}$
+\end_inset
+
+ con 
+\begin_inset Formula $s\neq\#$
+\end_inset
+
+ o 
+\begin_inset Formula $x_{ij\#}$
+\end_inset
+
+ con 
+\begin_inset Formula $j\neq0,t(n)+2$
+\end_inset
+
+ (que no están definidas y siempre son falsas).
+ Así, finalmente la fórmula es
+\begin_inset Formula 
+\[
+\Phi\coloneqq\Phi_{\text{start}}\land\Phi_{\text{accept}}\land\Phi_{\text{cell}}\land\Phi_{\text{move}}.
+\]
+
+\end_inset
+
+Si 
+\begin_inset Formula $t(n)=O(n^{k})$
+\end_inset
+
+, esta fórmula tiene 
+\begin_inset Formula $O(n^{2k})$
+\end_inset
+
+ variables (
+\begin_inset Formula $C$
+\end_inset
+
+ por celda), 
+\begin_inset Formula $\Phi_{\text{start}}$
+\end_inset
+
+ tiene 
+\begin_inset Formula $O(n^{k})$
+\end_inset
+
+ apariciones de variables (una por columna), 
+\begin_inset Formula $\Phi_{\text{accept}}$
+\end_inset
+
+ tiene 
+\begin_inset Formula $O(n^{2k})$
+\end_inset
+
+ (una por celda), 
+\begin_inset Formula $\Phi_{\text{cell}}$
+\end_inset
+
+ tiene 
+\begin_inset Formula $O(n^{2k})$
+\end_inset
+
+ (
+\begin_inset Formula $C^{2}$
+\end_inset
+
+ por celda) y 
+\begin_inset Formula $\Phi_{\text{move}}$
+\end_inset
+
+ tiene 
+\begin_inset Formula $O(2^{nk})$
+\end_inset
+
+ (hasta 6 por ventana legal y ventana, el número de ventanas legales es
+ fijo y hay menos ventanas que celdas).
+ Por tanto 
+\begin_inset Formula $\Phi$
+\end_inset
+
+ tiene tamaño 
+\begin_inset Formula $O(n^{2k})$
+\end_inset
+
+, y para 
+\begin_inset Formula $N$
+\end_inset
+
+ fijo, generarla a partir de 
+\begin_inset Formula $w$
+\end_inset
+
+ es sistemático, con lo que 
+\begin_inset Formula $\Phi$
+\end_inset
+
+ se genera en tiempo polinómico.
+\end_layout
+
+\begin_layout Standard
+Este teorema lo descubrieron Stephen Cook y Leonid Levin en los 70, siendo
+ 
+\begin_inset Formula $\text{SAT}$
+\end_inset
+
+ el primer lenguaje que se descubrió 
+\begin_inset Formula ${\cal NP}$
+\end_inset
+
+-completo.
+\end_layout
+
+\begin_layout Section
+Otros lenguajes 
+\begin_inset Formula ${\cal NP}$
+\end_inset
+
+-completos
+\end_layout
+
+\begin_layout Standard
+Un 
+\series bold
+literal
+\series default
+ es una variable o su negación.
+ Una 
+\series bold
+cláusula
+\series default
+ es una disyunción de uno o más literales.
+ Una fórmula booleana está en 
+\series bold
+forma normal conjuntiva
+\series default
+ si es una conjunción de una o más cláusulas, y está en 
+\series bold
+forma normal 3-conjuntiva
+\series default
+ si además estas cláusulas tienen un máximo de 3 literales.
+\end_layout
+
+\begin_layout Standard
+Llamando 
+\begin_inset Formula $\text{SAT}_{\text{CNF}}$
+\end_inset
+
+ al conjunto de fórmulas satisfacibles en forma normal conjuntiva y 
+\begin_inset Formula $\text{SAT}_{\text{3-CNF}}$
+\end_inset
+
+ al de fórmulas satisfacibles en forma normal 3-conjuntiva, 
+\begin_inset Formula $\text{SAT}_{\text{3-CNF}}\subsetneq\text{SAT}_{\text{CNF}}\subsetneq\text{SAT}$
+\end_inset
+
+, y 
+\begin_inset Formula $\text{SAT}_{\text{3-CNF}}$
+\end_inset
+
+ y 
+\begin_inset Formula $\text{SAT}_{\text{CNF}}$
+\end_inset
+
+ son 
+\begin_inset Formula ${\cal NP}$
+\end_inset
+
+-completos.
+ También lo son 
+\begin_inset Formula $\text{HAMPATH}$
+\end_inset
+
+ y 
+\begin_inset Formula $k\text{-CLIQUE}$
+\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
+ sus 
+\emph on
+\lang english
+papers
+\emph default
+\lang spanish
+ sobre el 
+\emph on
+\lang ngerman
+Entscheidungsproblem
+\emph default
+\lang spanish
+ en 1936.
+\end_layout
+
+\end_body
+\end_document