MC tema 7

4 files changed, 2358 insertions, 54 deletions

diff --git a/mc/n.lyx b/mc/n.lyx
index 79060b3..86ee807 100644
--- a/mc/n.lyx
+++ b/mc/n.lyx
@@ -236,6 +236,22 @@ end{sloppypar}
 
 \end_layout
 
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+SetAlgoVlined
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
 \begin_layout Chapter
 Lenguajes regulares
 \end_layout
@@ -320,5 +336,26 @@ filename "n6.lyx"
 
 \end_layout
 
+\begin_layout Chapter
+\begin_inset Formula ${\cal P}$
+\end_inset
+
+ y 
+\begin_inset Formula ${\cal NP}$
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+\begin_inset CommandInset include
+LatexCommand input
+filename "n7.lyx"
+
+\end_inset
+
+
+\end_layout
+
 \end_body
 \end_document
diff --git a/mc/n1.lyx b/mc/n1.lyx
index 42433c5..83907a6 100644
--- a/mc/n1.lyx
+++ b/mc/n1.lyx
@@ -203,6 +203,10 @@ Kleene star
 .
 \end_layout
 
+\begin_layout Section
+Autómatas finitos
+\end_layout
+
 \begin_layout Standard
 Un 
 \series bold
@@ -965,11 +969,8 @@ También podemos representar un NFA con una tabla con un estado por fila,
  cuyas celdas contienen los valores de la función de transición.
 \end_layout
 
-\begin_layout Standard
-\begin_inset Newpage pagebreak
-\end_inset
-
-
+\begin_layout Section
+Expresiones regulares
 \end_layout
 
 \begin_layout Standard
@@ -2092,6 +2093,14 @@ Recíprocamente, si
 \end_layout
 
 \end_deeper
+\begin_layout Section
+Propiedades de 
+\begin_inset Formula ${\cal REG}$
+\end_inset
+
+
+\end_layout
+
 \begin_layout Standard
 \begin_inset Formula ${\cal REG}$
 \end_inset
diff --git a/mc/n2.lyx b/mc/n2.lyx
index 2182537..6edfcc4 100644
--- a/mc/n2.lyx
+++ b/mc/n2.lyx
@@ -8,11 +8,13 @@
 \begin_preamble
 \input{../defs}
 \usepackage[x11names, svgnames, rgb]{xcolor}
-\usepackage[utf8]{inputenc}
 \usepackage{tikz}
 \usetikzlibrary{snakes,arrows,shapes}
 \end_preamble
 \use_default_options true
+\begin_modules
+algorithm2e
+\end_modules
 \maintain_unincluded_children false
 \language spanish
 \language_package default
@@ -84,6 +86,10 @@
 
 \begin_body
 
+\begin_layout Section
+Autómatas de pila
+\end_layout
+
 \begin_layout Standard
 Un 
 \series bold
@@ -508,6 +514,11 @@ Llamamos
 \end_inset
 
  a la de lenguajes aceptados por algún PDAD.
+ No todo lenguaje aceptado por un PDA es aceptado por un PDAD.
+\end_layout
+
+\begin_layout Section
+Gramáticas libres de contexto
 \end_layout
 
 \begin_layout Standard
@@ -664,6 +675,7 @@ libre de contexto
 \end_inset
 
  a la clase de los lenguajes libres de contexto.
+ Todo lenguaje generado por un PDA es libre de contexto.
 \end_layout
 
 \begin_layout Standard
@@ -726,6 +738,433 @@ derivación por la izquierda
 \end_layout
 
 \begin_layout Standard
+\begin_inset Float algorithm
+wide false
+sideways false
+status open
+
+\begin_layout Plain Layout
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+Entrada{GLC $G=(V,
+\backslash
+Sigma,{
+\backslash
+cal R},S)$.}
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+Salida{GLC $G'=(V,
+\backslash
+Sigma,{
+\backslash
+cal R},S_0)$ en forma normal de Chomsky con $L(G')=L(G)$.}
+\end_layout
+
+\begin_layout Plain Layout
+
+añadir una nueva variable $S_0$ a $V$
+\backslash
+;
+\end_layout
+
+\begin_layout Plain Layout
+
+añadir $S_0
+\backslash
+to S$ a ${
+\backslash
+cal R}$
+\backslash
+;
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+Para{$A
+\backslash
+to
+\backslash
+lambda
+\backslash
+in{
+\backslash
+cal R}$}{
+\end_layout
+
+\begin_layout Plain Layout
+
+	eliminar $A
+\backslash
+to
+\backslash
+varepsilon$ de ${
+\backslash
+cal R}$
+\backslash
+;
+\end_layout
+
+\begin_layout Plain Layout
+
+	
+\backslash
+Para{$B
+\backslash
+to w
+\backslash
+in{
+\backslash
+cal R}$ con $A$ en $w$}{
+\end_layout
+
+\begin_layout Plain Layout
+
+		añadir $B
+\backslash
+to w'$ a ${
+\backslash
+cal R}$ para cada $w'$ resultante de
+\end_layout
+
+\begin_layout Plain Layout
+
+		eliminar 1 o más ocurrencias de $A$ en $w$, con lo que si hay
+\end_layout
+
+\begin_layout Plain Layout
+
+		$n$ ocurrencias de $A$ se añaden $2^n-1$ reglas, con la
+\end_layout
+
+\begin_layout Plain Layout
+
+		excepción de que si habíamos eliminado $B
+\backslash
+to
+\backslash
+lambda$ no la
+\end_layout
+
+\begin_layout Plain Layout
+
+		volvemos a añadir
+\backslash
+;
+\end_layout
+
+\begin_layout Plain Layout
+
+	}
+\end_layout
+
+\begin_layout Plain Layout
+
+}
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+Mientras{exista $A
+\backslash
+to B
+\backslash
+in{
+\backslash
+cal R}$ con $B
+\backslash
+in V$}{
+\end_layout
+
+\begin_layout Plain Layout
+
+	eliminar $A
+\backslash
+to B$ de ${
+\backslash
+cal R}$
+\backslash
+;
+\end_layout
+
+\begin_layout Plain Layout
+
+	
+\backslash
+SSi{$A
+\backslash
+neq B$}{
+\end_layout
+
+\begin_layout Plain Layout
+
+		
+\backslash
+lPara{$B
+\backslash
+to u
+\backslash
+in{
+\backslash
+cal R}$}{añadir $A
+\backslash
+to u$ a $R$}
+\end_layout
+
+\begin_layout Plain Layout
+
+	}
+\end_layout
+
+\begin_layout Plain Layout
+
+}
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+Para{$A
+\backslash
+to u_1
+\backslash
+cdots u_k
+\backslash
+in{
+\backslash
+cal R}$ con $k
+\backslash
+geq3$}{
+\end_layout
+
+\begin_layout Plain Layout
+
+	eliminar $A
+\backslash
+to u_1
+\backslash
+cdots u_k$ de ${
+\backslash
+cal R}$
+\backslash
+;
+\end_layout
+
+\begin_layout Plain Layout
+
+	añadir nuevas variables $A_1,
+\backslash
+dots,A_{k-2}$ a $V$
+\backslash
+;
+\end_layout
+
+\begin_layout Plain Layout
+
+	
+\backslash
+lPara{$i
+\backslash
+gets1$ a $k-3$}{añadir $A_i
+\backslash
+to u_{i+1}A_{i+1}$ a ${
+\backslash
+cal R}$}
+\end_layout
+
+\begin_layout Plain Layout
+
+	añadir $A
+\backslash
+to u_1A_1$ y $A_{k-2}
+\backslash
+to u_{k-1}u_k$ a $R$
+\backslash
+;
+\end_layout
+
+\begin_layout Plain Layout
+
+}
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+Para{$X
+\backslash
+to ab$ con $a
+\backslash
+in
+\backslash
+Sigma$ o $b
+\backslash
+in
+\backslash
+Sigma$}{
+\end_layout
+
+\begin_layout Plain Layout
+
+	
+\backslash
+SSi{$a
+\backslash
+in
+\backslash
+Sigma$}{
+\end_layout
+
+\begin_layout Plain Layout
+
+		añadir una nueva variable $A$ a $V$ y $A
+\backslash
+to a$ a ${
+\backslash
+cal R}$
+\backslash
+;
+\end_layout
+
+\begin_layout Plain Layout
+
+		cambiar $X
+\backslash
+to ab$ por $X
+\backslash
+to Ab$
+\backslash
+;
+\end_layout
+
+\begin_layout Plain Layout
+
+	}
+\end_layout
+
+\begin_layout Plain Layout
+
+	
+\backslash
+lSSi{$b
+\backslash
+in
+\backslash
+Sigma$}{hacer lo propio}
+\end_layout
+
+\begin_layout Plain Layout
+
+}
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Plain Layout
+\begin_inset Caption Standard
+
+\begin_layout Plain Layout
+\begin_inset CommandInset label
+LatexCommand label
+name "alg:chomsky"
+
+\end_inset
+
+Conversión de una GLC a forma normal de Chomsky.
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+Una GLC está en 
+\series bold
+forma normal de Chomsky
+\series default
+ si todas sus reglas son de la forma 
+\begin_inset Formula $S\to\lambda$
+\end_inset
+
+, 
+\begin_inset Formula $A\to BC$
+\end_inset
+
+ o 
+\begin_inset Formula $A\to a$
+\end_inset
+
+, donde 
+\begin_inset Formula $S$
+\end_inset
+
+ es la variable inicial, 
+\begin_inset Formula $A$
+\end_inset
+
+, 
+\begin_inset Formula $B$
+\end_inset
+
+ y 
+\begin_inset Formula $C$
+\end_inset
+
+ son variables arbitrarias con 
+\begin_inset Formula $B,C\neq S$
+\end_inset
+
+ y 
+\begin_inset Formula $a$
+\end_inset
+
+ es un terminal arbitrario.
+ Toda GLC se puede convertir a forma normal de Chomsky con el Algoritmo
+ 
+\begin_inset CommandInset ref
+LatexCommand ref
+reference "alg:chomsky"
+plural "false"
+caps "false"
+noprefix "false"
+
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Section
+Propiedades de 
+\begin_inset Formula ${\cal CF}$
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
 Como 
 \series bold
 teorema
@@ -858,7 +1297,7 @@ small
 
 
 \backslash
-input{n2.1.tex} % dot -Txdot n2.1.dot | dot2tex --codeonly >n2.1.tex
+input{n2.1.tex}% dot -Txdot n2.1.dot | dot2tex --codeonly >n2.1.tex
 \end_layout
 
 \begin_layout Plain Layout
@@ -879,18 +1318,17 @@ end{tikzpicture}
 \end_inset
 
  Por definición.
-\begin_inset Note Comment
-status open
+\end_layout
 
 \begin_layout Description
 \begin_inset Formula $3\subseteq4]$
 \end_inset
 
- Dado un PDA 
+ Un PDA 
 \begin_inset Formula ${\cal A}=(Q,\Sigma,\Gamma,\delta,A_{0},q_{0},F)$
 \end_inset
 
-, el PDA
+ acepta el mismo lenguaje que el PDA
 \begin_inset Formula $^{\text{v}}$
 \end_inset
 
@@ -906,14 +1344,18 @@ status open
 \delta(q,a,x)\cup\{(q_{\text{e}},\epsilon)\}, & q\in F\land a,x=\epsilon;\\
 \delta(q,a,x), & q\in Q\land\neg(q\in F\land a,x=\epsilon);\\
 \{(q_{\text{e}},\epsilon)\}, & q=q_{\text{e}}\land a=\epsilon\land x\neq\epsilon;\\
-\emptyset, & \text{en otro caso},
+\emptyset, & \text{en otro caso}.
 \end{cases}
 \]
 
 \end_inset
 
-acepta el mismo lenguaje.
- En efecto, si 
+
+\begin_inset Note Comment
+status open
+
+\begin_layout Plain Layout
+En efecto, si 
 \begin_inset Formula $s_{0}\cdots s_{k}$
 \end_inset
 
@@ -1040,11 +1482,16 @@ acepta el mismo lenguaje.
  al fondo de la pila en cada posición).
 \end_layout
 
+\end_inset
+
+
+\end_layout
+
 \begin_layout Description
 \begin_inset Formula $4\subseteq3]$
 \end_inset
 
- Dado un PDA
+ Un PDA
 \begin_inset Formula $^{\text{v}}$
 \end_inset
 
@@ -1052,7 +1499,7 @@ acepta el mismo lenguaje.
 \begin_inset Formula ${\cal A}'\coloneqq(Q,\Sigma,\Gamma,\delta,A_{0},q_{0})$
 \end_inset
 
-, el PDA dado por 
+ acepta el mismo lenguaje que el PDA dado por 
 \begin_inset Formula ${\cal A}\coloneqq(Q\sqcup\{q_{\text{s}}\}\sqcup\{q_{\text{e}}\},\Sigma,\Gamma\sqcup\{\$\},\delta',\$,q_{\text{s}},\{q_{\text{e}}\})$
 \end_inset
 
@@ -1069,6 +1516,11 @@ acepta el mismo lenguaje.
 
 \end_inset
 
+
+\begin_inset Note Comment
+status open
+
+\begin_layout Plain Layout
 En efecto, si 
 \begin_inset Formula $s_{0}\cdots s_{k}$
 \end_inset
@@ -1195,9 +1647,9 @@ cumple
 \end_inset
 
 .
-\end_layout
+\begin_inset Note Comment
+status open
 
-\begin_deeper
 \begin_layout Itemize
 \begin_inset Argument item:1
 status open
@@ -1269,6 +1721,7 @@ nte y se elimina el símbolo de la pila, y por inducción sobre la altura
 .
 \end_layout
 
+\begin_deeper
 \begin_layout Itemize
 \begin_inset Argument item:1
 status open
@@ -1373,6 +1826,11 @@ Sean
 \end_layout
 
 \end_deeper
+\end_inset
+
+
+\end_layout
+
 \begin_layout Standard
 
 \series bold
@@ -1661,22 +2119,6 @@ Demostración:
 \end_layout
 
 \begin_layout Standard
-\begin_inset ERT
-status open
-
-\begin_layout Plain Layout
-
-
-\backslash
-begin{samepage}
-\end_layout
-
-\end_inset
-
-
-\end_layout
-
-\begin_layout Standard
 Dados 
 \begin_inset Formula $L_{1},L_{2}\in{\cal CF}$
 \end_inset
@@ -1928,7 +2370,12 @@ En general
 \begin_inset Formula $L_{2}\coloneqq\{a^{m}b^{n}c^{n}\}_{n,m\in\mathbb{N}}$
 \end_inset
 
- son libres de contexto, pues vienen dados respectivamente por
+ son libres de contexto,
+\begin_inset Note Comment
+status open
+
+\begin_layout Plain Layout
+pues vienen dados respectivamente por
 \begin_inset Formula 
 \begin{eqnarray*}
 \begin{array}{rl}
@@ -1944,7 +2391,12 @@ B & \to bBc\mid\epsilon
 
 \end_inset
 
-pero 
+
+\end_layout
+
+\end_inset
+
+ pero 
 \begin_inset Formula $L_{1}\cap L_{2}=\{a^{n}b^{n}c^{n}\}_{n\in\mathbb{N}}\notin{\cal CF}$
 \end_inset
 
@@ -1993,24 +2445,8 @@ Si lo fuera, como
 
 \end_deeper
 \begin_layout Standard
-\begin_inset ERT
-status open
-
-\begin_layout Plain Layout
-
-
-\backslash
-end{samepage}
-\end_layout
-
-\end_inset
-
-
-\end_layout
-
-\begin_layout Standard
-Los autómatas de pila no son un buen modelo de computación, pues esperaríamos
- que un ordenador pudiera reconocer si una cadena está en 
+Los autómatas de pila no son un buen modelo de computación, pues un ordenador
+ puede reconocer si una cadena está en 
 \begin_inset Formula $\{a^{n}b^{n}c^{n}\}_{n\in\mathbb{N}}$
 \end_inset
 
diff --git a/mc/n7.lyx b/mc/n7.lyx
new file mode 100644
index 0000000..9bfe853
--- /dev/null
+++ b/mc/n7.lyx
@@ -0,0 +1,1822 @@
+#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
+Un problema es 
+\series bold
+tratable
+\series default
+ si se puede resolver de forma suficientemente eficiente, y es 
+\series bold
+intratable
+\series default
+ si se puede resolver pero no lo suficientemente rápido como para que la
+ 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}$
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+Un lenguaje es 
+\series bold
+decidible en tiempo polinómico
+\series default
+ si está en
+\begin_inset Formula 
+\[
+{\cal P}\coloneqq\bigcup_{k}\text{TIME}(n^{k}).
+\]
+
+\end_inset
+
+Los problemas en esta clase se consideran tratables, y el resto intratables.
+ Así, son intratables los problemas con orden de complejidad exponencial,
+ que suelen corresponder a búsqueda exhaustiva o por fuerza bruta del espacio
+ de búsqueda, y que solo se pueden resolver de forma general en casos sencillos.
+ Realmente, si un problema en 
+\begin_inset Formula $\text{TIME}(n^{k})$
+\end_inset
+
+ es tratable depende de 
+\begin_inset Formula $k$
+\end_inset
+
+ y de la aplicación particular, pero la distinción entre tiempo polinómico
+ y exponencial es útil en la práctica.
+\end_layout
+
+\begin_layout Standard
+\begin_inset Formula ${\cal P}$
+\end_inset
+
+ no es afectada significativamente por las particularidades del modelo de
+ computación, y de hecho es igual para una 
+\begin_inset Formula $\text{MT}$
+\end_inset
+
+, una 
+\begin_inset Formula $k\text{-MT}$
+\end_inset
+
+ y un ordenador típico (extendido para que sea Turing-completo).
+ Sin embargo, sí es afectada por la representación del problema, pues aunque
+ casi todas las representaciones son equivalentes a este respecto, no todas
+ lo son.
+\end_layout
+
+\begin_layout Standard
+Una representación es 
+\series bold
+razonable
+\series default
+ si permite codificar y decodificar objetos hacia una representación interna
+ en tiempo polinómico.
+\begin_inset Foot
+status open
+
+\begin_layout Plain Layout
+Esto es así pese a que no hemos definido 
+\begin_inset Quotes cld
+\end_inset
+
+representación interna
+\begin_inset Quotes crd
+\end_inset
+
+ y en principio esta depende de la implementación del algoritmo.
+\end_layout
+
+\end_inset
+
+ Las formas que hemos usado para representar autómatas, grafos, etc.
+ son razonables, pero no lo es la representación unaria de números, pues
+ es exponencialmente más larga que una representación en base 2 o más.
+\end_layout
+
+\begin_layout Standard
+\begin_inset Float algorithm
+wide false
+sideways false
+status open
+
+\begin_layout Plain Layout
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+Entrada{Cadena $a$
+\backslash
+textvisiblespace{}$b$, donde $a,b
+\backslash
+in
+\backslash
+{0,1
+\backslash
+}^*$ son números naturales representados empezando por el bit menos significativ
+o.}
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+Salida{Número $a+b$ con la misma representación.}
+\end_layout
+
+\begin_layout Plain Layout
+
+avanzar hasta 
+\backslash
+textvisiblespace{}, borrarlo y mover el resto a la cinta 2
+\backslash
+;
+\end_layout
+
+\begin_layout Plain Layout
+
+volver al principio
+\backslash
+;
+\end_layout
+
+\begin_layout Plain Layout
+
+$c
+\backslash
+gets0$
+\backslash
+;
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+Mientras{no hay $B$ en ambas cintas}{
+\end_layout
+
+\begin_layout Plain Layout
+
+	leer $a$ de cinta 1 y $b$ de 2
+\backslash
+;
+\end_layout
+
+\begin_layout Plain Layout
+
+	escribir $a+b+c
+\backslash
+bmod 2$ en cinta 1 y B en 2
+\backslash
+;
+\end_layout
+
+\begin_layout Plain Layout
+
+	hacer $c
+\backslash
+gets[a+b+c
+\backslash
+geq2]$ y avanzar
+\backslash
+;
+\end_layout
+
+\begin_layout Plain Layout
+
+}
+\end_layout
+
+\begin_layout Plain Layout
+
+volver al principio
+\backslash
+;
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Plain Layout
+\begin_inset Caption Standard
+
+\begin_layout Plain Layout
+\begin_inset CommandInset label
+LatexCommand label
+name "alg:suma"
+
+\end_inset
+
+Suma 
+\begin_inset Formula $O(n)$
+\end_inset
+
+ en 
+\begin_inset Formula $\text{2-MT}$
+\end_inset
+
+.
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+\begin_inset Float algorithm
+wide false
+sideways false
+status open
+
+\begin_layout Plain Layout
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+Entrada{Como en Algoritmo 
+\backslash
+ref{alg:suma}.}
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+Salida{$
+\backslash
+max
+\backslash
+{a-b,0
+\backslash
+}$.}
+\end_layout
+
+\begin_layout Plain Layout
+
+avanzar hasta 
+\backslash
+textvisiblespace{}, borrarlo y mover el resto a la cinta 2
+\backslash
+;
+\end_layout
+
+\begin_layout Plain Layout
+
+volver al principio
+\backslash
+;
+\end_layout
+
+\begin_layout Plain Layout
+
+$c
+\backslash
+gets0$
+\backslash
+;
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+Mientras{no hay $B$ en ambas cintas}{
+\end_layout
+
+\begin_layout Plain Layout
+
+	leer $a$ de cinta 1 y $b$ de 2
+\backslash
+;
+\end_layout
+
+\begin_layout Plain Layout
+
+	escribir $a-b-c
+\backslash
+bmod 2$ en cinta 1 y B en 2
+\backslash
+;
+\end_layout
+
+\begin_layout Plain Layout
+
+	hacer $c
+\backslash
+gets[a-b-c<0]$ y avanzar
+\backslash
+;
+\end_layout
+
+\begin_layout Plain Layout
+
+}
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+lSSi{$c=1$}{borrar toda la cinta 1 y escribir <<0>>}
+\end_layout
+
+\begin_layout Plain Layout
+
+volver al principio
+\backslash
+;
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Plain Layout
+\begin_inset Caption Standard
+
+\begin_layout Plain Layout
+\begin_inset CommandInset label
+LatexCommand label
+name "alg:resta"
+
+\end_inset
+
+Resta saturada 
+\begin_inset Formula $O(n)$
+\end_inset
+
+ en 
+\begin_inset Formula $\text{2-MT}$
+\end_inset
+
+.
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+\begin_inset Float algorithm
+wide false
+sideways false
+status open
+
+\begin_layout Plain Layout
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+Entrada{Como en Algoritmo 
+\backslash
+ref{alg:suma}.}
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+Salida{$ab$.}
+\end_layout
+
+\begin_layout Plain Layout
+
+tras el final de la cadena escribir 
+\backslash
+textvisiblespace{}
+\backslash
+;
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+Mientras{haya un símbolo no marcado antes del primer 
+\backslash
+textvisiblespace{}}{
+\end_layout
+
+\begin_layout Plain Layout
+
+	marcarlo y guardarlo en $c$
+\backslash
+;
+\end_layout
+
+\begin_layout Plain Layout
+
+	
+\backslash
+lSSi{$c=1$}{copiar $b$ al final precedido por 
+\backslash
+textvisiblespace}
+\end_layout
+
+\begin_layout Plain Layout
+
+	ir al primer caracter no marcado tras el segundo 
+\backslash
+textvisiblespace{}
+\backslash
+;
+\end_layout
+
+\begin_layout Plain Layout
+
+	
+\backslash
+lSSi{$c=1$}{ejecutar el Algoritmo 
+\backslash
+ref{alg:suma} para sumar}
+\end_layout
+
+\begin_layout Plain Layout
+
+	marcar el caracter actual
+\backslash
+;
+\end_layout
+
+\begin_layout Plain Layout
+
+}
+\end_layout
+
+\begin_layout Plain Layout
+
+borrar desde el principio hasta el segundo 
+\backslash
+textvisiblespace{} desplazando a la izquierda
+\backslash
+;
+\end_layout
+
+\begin_layout Plain Layout
+
+eliminar las marcas
+\backslash
+;
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Plain Layout
+\begin_inset Caption Standard
+
+\begin_layout Plain Layout
+\begin_inset CommandInset label
+LatexCommand label
+name "alg:producto"
+
+\end_inset
+
+Producto 
+\begin_inset Formula $O(n^{3})$
+\end_inset
+
+ en 
+\begin_inset Formula $\text{MT}$
+\end_inset
+
+.
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+\begin_inset Float algorithm
+wide false
+sideways false
+status open
+
+\begin_layout Plain Layout
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+Entrada{Números $a$ y $b$ separados por 
+\backslash
+textvisiblespace{}, en binario con el bit menos significativo a la izquierda.}
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+Salida{Resto y cociente de $b/a$ separados por 
+\backslash
+textvisiblespace{}.}
+\end_layout
+
+\begin_layout Plain Layout
+
+escribir <<
+\backslash
+textvisiblespace{}>> al final de la cadena
+\backslash
+;
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+Mientras{$b>a$}{
+\end_layout
+
+\begin_layout Plain Layout
+
+	
+\backslash
+lMientras{haya un dígito de $a$ sin marcar}{marcar un dígito de $a$ y $b$
+ más a la derecha que no esté marcado}
+\end_layout
+
+\begin_layout Plain Layout
+
+	
+\backslash
+Mientras{la parte marcada de $b$ es menor que la de $a$}{
+\end_layout
+
+\begin_layout Plain Layout
+
+		marcar el dígito sin marcar de $b$ más a la derecha
+\backslash
+;
+\end_layout
+
+\begin_layout Plain Layout
+
+		insertar un 0 detrás del segundo 
+\backslash
+textvisiblespace{}
+\backslash
+;
+\end_layout
+
+\begin_layout Plain Layout
+
+	}
+\end_layout
+
+\begin_layout Plain Layout
+
+	copiar la parte marcada de $b$, sin las marcas, al final
+\backslash
+;
+\end_layout
+
+\begin_layout Plain Layout
+
+    escribir 
+\backslash
+textvisiblespace{} y hacer lo propio con $a$
+\backslash
+;
+\end_layout
+
+\begin_layout Plain Layout
+
+	ejecutar el Algoritmo 
+\backslash
+ref{alg:resta} para restar
+\backslash
+;
+\end_layout
+
+\begin_layout Plain Layout
+
+	mover el resultado sobre la parte marcada de $b$, de derecha a izquierda,
+ cambiando el primer caracter de $b$ por 0 si no se había reemplazado
+\backslash
+;
+\end_layout
+
+\begin_layout Plain Layout
+
+	ir al principio de $b$
+\backslash
+;
+\end_layout
+
+\begin_layout Plain Layout
+
+	
+\backslash
+lMientras{$0$}{eliminar desplazando lo de detrás a la izquierda}
+\end_layout
+
+\begin_layout Plain Layout
+
+	insertar un 1 detrás del segundo 
+\backslash
+textvisiblespace{}
+\backslash
+;
+\end_layout
+
+\begin_layout Plain Layout
+
+}
+\end_layout
+
+\begin_layout Plain Layout
+
+eliminar $a$
+\backslash
+textvisiblespace{} desplazando lo de detrás a la izquierda
+\backslash
+;
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Plain Layout
+\begin_inset Caption Standard
+
+\begin_layout Plain Layout
+\begin_inset CommandInset label
+LatexCommand label
+name "alg:cociente"
+
+\end_inset
+
+Cociente entero 
+\begin_inset Formula $O(n^{3})$
+\end_inset
+
+ en 
+\begin_inset Formula $\text{MT}$
+\end_inset
+
+, usando que comparar dos números claramente se puede hacer en 
+\begin_inset Formula $O(n^{2})$
+\end_inset
+
+.
+ Aunque esta comparación se hace en un bucle dentro de otro, a cada comparación
+ le corresponde la inserción de un dígito en el cociente y hay 
+\begin_inset Formula $O(n)$
+\end_inset
+
+ de estas inserciones.
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+\begin_inset Float algorithm
+wide false
+sideways false
+status open
+
+\begin_layout Plain Layout
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+Entrada{Gramática $G=(V,
+\backslash
+Sigma,{
+\backslash
+cal R},S)$ en forma normal de Chomsky y cadena $w_1
+\backslash
+cdots w_n
+\backslash
+in
+\backslash
+Sigma$.}
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+Salida{Acepta si $w
+\backslash
+in L(G)$, rechaza en otro caso.}
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+SSi{$w=
+\backslash
+lambda$}{
+\end_layout
+
+\begin_layout Plain Layout
+
+	
+\backslash
+lSSi{$S
+\backslash
+to
+\backslash
+lambda
+\backslash
+in{
+\backslash
+cal R}$}{aceptar}
+\end_layout
+
+\begin_layout Plain Layout
+
+	
+\backslash
+lEnOtroCaso{rechazar}
+\end_layout
+
+\begin_layout Plain Layout
+
+}
+\end_layout
+
+\begin_layout Plain Layout
+
+$T
+\backslash
+gets
+\backslash
+emptyset$
+\end_layout
+
+\begin_layout Plain Layout
+
+	
+\backslash
+tcp*{{
+\backslash
+rm Para $
+\backslash
+{(i,j)
+\backslash
+}_{1
+\backslash
+leq i<j
+\backslash
+leq n}$, $T(i,j)$ contiene las variables que generan $w_i
+\backslash
+cdots w_j$.}}
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+Para{$i
+\backslash
+gets1$ 
+\backslash
+KwA $n$}{
+\end_layout
+
+\begin_layout Plain Layout
+
+	
+\backslash
+lPara{$A
+\backslash
+in V$ con $A
+\backslash
+to w_i
+\backslash
+in{
+\backslash
+cal R}$}{añadir $A$ a $T(i,i)$}
+\end_layout
+
+\begin_layout Plain Layout
+
+}
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+Para{$l
+\backslash
+gets2$ 
+\backslash
+KwA $n$}{
+\end_layout
+
+\begin_layout Plain Layout
+
+	
+\backslash
+Para{$i=1$ 
+\backslash
+KwA $n-l+1$}{
+\end_layout
+
+\begin_layout Plain Layout
+
+		$j
+\backslash
+gets i+l-1$
+\backslash
+;
+\end_layout
+
+\begin_layout Plain Layout
+
+		
+\backslash
+Para{$k
+\backslash
+gets i$ 
+\backslash
+KwA $j-1$}{
+\end_layout
+
+\begin_layout Plain Layout
+
+			
+\backslash
+Para{$A
+\backslash
+to BC
+\backslash
+in{
+\backslash
+cal R}$}{
+\end_layout
+
+\begin_layout Plain Layout
+
+				
+\backslash
+lSSi{$B
+\backslash
+in T(i,k)$ y $C
+\backslash
+in T(k+1,j)$}{añadir $A$ a $T(i,j)$}
+\end_layout
+
+\begin_layout Plain Layout
+
+			}
+\end_layout
+
+\begin_layout Plain Layout
+
+		}
+\end_layout
+
+\begin_layout Plain Layout
+
+	}
+\end_layout
+
+\begin_layout Plain Layout
+
+}
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+lSSi{$S
+\backslash
+in T(1,n)$}{aceptar}
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+lEnOtroCaso{rechazar}
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Plain Layout
+\begin_inset Caption Standard
+
+\begin_layout Plain Layout
+\begin_inset CommandInset label
+LatexCommand label
+name "alg:cyk"
+
+\end_inset
+
+Algoritmo CYK de programación dinámica para establecer si una cadena está
+ en un cierto lenguaje libre de contexto en tiempo polinómico.
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+Están en 
+\begin_inset Formula ${\cal P}$
+\end_inset
+
+:
+\end_layout
+
+\begin_layout Enumerate
+\begin_inset Formula $\text{RELPRIM}\coloneqq\{\langle x,y\rangle:x,y\in\mathbb{N}\text{ son primos relativos}\}$
+\end_inset
+
+.
+\end_layout
+
+\begin_deeper
+\begin_layout Standard
+Una forma de comprobarlo es usar el algoritmo de Euclides para ver que 
+\begin_inset Formula $\gcd\{x,y\}=1$
+\end_inset
+
+, repitiendo 
+\begin_inset Formula $(x,y)\gets(y,x\bmod y)$
+\end_inset
+
+ hasta que 
+\begin_inset Formula $y=0$
+\end_inset
+
+.
+ La operación más cara en un paso es el módulo, 
+\begin_inset Formula $O(n^{3})$
+\end_inset
+
+ con el Algoritmo 
+\begin_inset CommandInset ref
+LatexCommand ref
+reference "alg:cociente"
+plural "false"
+caps "false"
+noprefix "false"
+
+\end_inset
+
+, y basta ver que el número de pasos es polinómico respecto al tamaño de
+ la entrada, para lo que vemos que, excluyendo el primer paso, cada 2 pasos
+ 
+\begin_inset Formula $x$
+\end_inset
+
+ se divide al menos por la mitad.
+ En efecto, tras el primer paso 
+\begin_inset Formula $x>y$
+\end_inset
+
+, de modo que si 
+\begin_inset Formula $\frac{x}{2}\geq y$
+\end_inset
+
+, 
+\begin_inset Formula $x\bmod y<y\leq\frac{x}{2}$
+\end_inset
+
+, y si 
+\begin_inset Formula $\frac{x}{2}<y$
+\end_inset
+
+, 
+\begin_inset Formula $x\bmod y=x-y<\frac{x}{2}$
+\end_inset
+
+, pero 
+\begin_inset Formula $x\bmod y$
+\end_inset
+
+ será el valor de 
+\begin_inset Formula $y$
+\end_inset
+
+ en un paso y de 
+\begin_inset Formula $x$
+\end_inset
+
+ en dos.
+\end_layout
+
+\end_deeper
+\begin_layout Enumerate
+\begin_inset Formula $\text{PATH}\coloneqq\{\langle G,s,t\rangle:G\text{ es un grafo dirigido con un camino de }s\text{ a }t\}$
+\end_inset
+
+.
+\end_layout
+
+\begin_deeper
+\begin_layout Standard
+Se añade el nodo 
+\begin_inset Formula $s$
+\end_inset
+
+ a una lista 
+\begin_inset Formula $F$
+\end_inset
+
+.
+ Mientras haya un nodo 
+\begin_inset Formula $n$
+\end_inset
+
+ en 
+\begin_inset Formula $F$
+\end_inset
+
+, se elimina de 
+\begin_inset Formula $n$
+\end_inset
+
+, se añade a 
+\begin_inset Formula $C$
+\end_inset
+
+, se recorren los arcos añadiendo a 
+\begin_inset Formula $F$
+\end_inset
+
+ los que parten de 
+\begin_inset Formula $n$
+\end_inset
+
+ y van a un nodo que no está 
+\begin_inset Formula $C$
+\end_inset
+
+.
+ Se acepta si y sólo si 
+\begin_inset Formula $t$
+\end_inset
+
+ está en 
+\begin_inset Formula $C$
+\end_inset
+
+.
+\end_layout
+
+\end_deeper
+\begin_layout Enumerate
+\begin_inset Formula $\text{4-CLIQUE}\coloneqq\{\langle G\rangle:G\text{ es un grafo no dirigido con una 4-clique}\}$
+\end_inset
+
+.
+\end_layout
+
+\begin_deeper
+\begin_layout Standard
+Si 
+\begin_inset Formula $G$
+\end_inset
+
+ tiene menos de 4 nodos, rechaza.
+ En otro caso se enumeran las 
+\begin_inset Formula $\binom{n}{4}=\frac{n!}{4!(n-4)!}=O(n^{4})$
+\end_inset
+
+ combinaciones de 4 nodos y, para cada una, se comprueba si todos los pares
+ de nodos están en el grafo.
+\end_layout
+
+\end_deeper
+\begin_layout Enumerate
+Todo 
+\begin_inset Formula $L\in{\cal CF}$
+\end_inset
+
+.
+\end_layout
+
+\begin_deeper
+\begin_layout Standard
+Algoritmo 
+\begin_inset CommandInset ref
+LatexCommand ref
+reference "alg:cyk"
+plural "false"
+caps "false"
+noprefix "false"
+
+\end_inset
+
+.
+\end_layout
+
+\end_deeper
+\begin_layout Standard
+Dados 
+\begin_inset Formula $L_{1},L_{2}\in{\cal P}$
+\end_inset
+
+, 
+\begin_inset Formula $L_{1}\cup L_{2},L_{1}\cap L_{2},\overline{L_{1}},L_{1}L_{2},L_{1}^{*}\in{\cal P}$
+\end_inset
+
+.
+ 
+\series bold
+Demostración:
+\series default
+ La unión, intersección y clausura son triviales.
+ Respecto a la concatenación, para cada partición de la entrada en 2 partes,
+ posiblemente vacías, se decide 
+\begin_inset Formula $L_{1}$
+\end_inset
+
+ en la primera y 
+\begin_inset Formula $L_{2}$
+\end_inset
+
+ en la segunda.
+ Para ver que 
+\begin_inset Formula $L_{1}^{*}\in{\cal P}$
+\end_inset
+
+, hacemos lo siguiente: Para una entrada 
+\begin_inset Formula $w_{1}\cdots w_{n}$
+\end_inset
+
+, si 
+\begin_inset Formula $n=0$
+\end_inset
+
+, acepta.
+ En otro caso se usa una programación dinámica con una tabla 
+\begin_inset Formula $T(i,j)$
+\end_inset
+
+ en la que, para 
+\begin_inset Formula $1\leq i<j\leq n$
+\end_inset
+
+, 
+\begin_inset Formula $T(i,j)$
+\end_inset
+
+ indica si 
+\begin_inset Formula $w_{i}\cdots w_{j}\in L_{1}^{*}$
+\end_inset
+
+.
+ Para 
+\begin_inset Formula $l$
+\end_inset
+
+ de 1 a 
+\begin_inset Formula $n$
+\end_inset
+
+, para 
+\begin_inset Formula $i$
+\end_inset
+
+ de 1 a 
+\begin_inset Formula $n-l+1$
+\end_inset
+
+, sea 
+\begin_inset Formula $j=i+l-1$
+\end_inset
+
+, si 
+\begin_inset Formula $w_{i}\cdots w_{j}\in L_{1}$
+\end_inset
+
+, se marca 
+\begin_inset Formula $T(i,j)$
+\end_inset
+
+, y de lo contrario, para 
+\begin_inset Formula $k$
+\end_inset
+
+ de 
+\begin_inset Formula $i$
+\end_inset
+
+ a 
+\begin_inset Formula $j-1$
+\end_inset
+
+, si están marcadas 
+\begin_inset Formula $T(i,k)$
+\end_inset
+
+ y 
+\begin_inset Formula $T(k+1,j)$
+\end_inset
+
+, se marca 
+\begin_inset Formula $T(i,j)$
+\end_inset
+
+.
+ Finalmente se acepta o rechaza según 
+\begin_inset Formula $T(1,n)$
+\end_inset
+
+ esté marcada o no.
+ En total se hacen 
+\begin_inset Formula $O(n^{3})$
+\end_inset
+
+ consultas a 
+\begin_inset Formula $T$
+\end_inset
+
+ y 
+\begin_inset Formula $O(n^{2})$
+\end_inset
+
+ ejecuciones de la máquina que decide 
+\begin_inset Formula $L_{1}$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Section
+La clase 
+\begin_inset Formula ${\cal NP}$
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+Dada una clase 
+\begin_inset Formula ${\cal C}$
+\end_inset
+
+ de problemas que una 
+\begin_inset Formula $\text{MT}$
+\end_inset
+
+ puede solucionar con un cierto orden de complejidad en tiempo, llamamos
+ 
+\begin_inset Formula ${\cal NC}$
+\end_inset
+
+ a la clase de problemas que una 
+\begin_inset Formula $\text{MTND}$
+\end_inset
+
+ puede solucionar en dicho orden de complejidad.
+\end_layout
+
+\begin_layout Standard
+Así, un lenguaje es 
+\begin_inset Formula $\text{NTIME}(f(n))$
+\end_inset
+
+ si existe una 
+\begin_inset Formula $\text{MTND}$
+\end_inset
+
+ que lo decide con complejidad en tiempo 
+\begin_inset Formula $O(f(n))$
+\end_inset
+
+, y 
+\begin_inset Formula 
+\[
+{\cal NP}=\bigcup_{k}\text{NTIME}(n^{k}).
+\]
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+begin{samepage}
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+Un 
+\series bold
+verificador
+\series default
+ para un lenguaje 
+\begin_inset Formula $L$
+\end_inset
+
+ es un algoritmo 
+\begin_inset Formula $V$
+\end_inset
+
+ tal que 
+\begin_inset Formula $L=\{w:\exists c:V\text{ acepta }\langle w,c\rangle\}$
+\end_inset
+
+.
+ Un lenguaje 
+\begin_inset Formula $L$
+\end_inset
+
+ es 
+\begin_inset Formula ${\cal NP}$
+\end_inset
+
+ si y sólo si tiene un verificador que se ejecuta en tiempo 
+\begin_inset Formula $O(|w|^{k})$
+\end_inset
+
+ para algún 
+\begin_inset Formula $k$
+\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
+
+Sea 
+\begin_inset Formula $M$
+\end_inset
+
+ una 
+\begin_inset Formula $\text{MTND}$
+\end_inset
+
+ que decide 
+\begin_inset Formula $L$
+\end_inset
+
+ en tiempo polinómico, definimos un verificador que, ante una entrada 
+\begin_inset Formula $\langle w,c\rangle$
+\end_inset
+
+, simula 
+\begin_inset Formula $M$
+\end_inset
+
+ tratando 
+\begin_inset Formula $c$
+\end_inset
+
+ como una secuencia con la opción que hace 
+\begin_inset Formula $M$
+\end_inset
+
+ en cada paso para aceptar 
+\begin_inset Formula $w$
+\end_inset
+
+, y que acepta o rechaza según lo haga 
+\begin_inset Formula $M$
+\end_inset
+
+ con esta configuración.
+\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
+
+Sea 
+\begin_inset Formula $V$
+\end_inset
+
+ el verificador en tiempo 
+\begin_inset Formula $O(|w|^{k})$
+\end_inset
+
+, por definición existen 
+\begin_inset Formula $m,c\in\mathbb{N}$
+\end_inset
+
+ tales que, para toda cadena 
+\begin_inset Formula $w$
+\end_inset
+
+, 
+\begin_inset Formula $V$
+\end_inset
+
+ se ejecuta en tiempo máximo 
+\begin_inset Formula $t(w)\coloneqq\max\{m,c|w|^{k}\}$
+\end_inset
+
+.
+ Definimos una 
+\begin_inset Formula $\text{MTND}$
+\end_inset
+
+ que, ante una entrada 
+\begin_inset Formula $w$
+\end_inset
+
+, elige de forma no determinista una cadena 
+\begin_inset Formula $c$
+\end_inset
+
+ de longitud máxima 
+\begin_inset Formula $t(w)$
+\end_inset
+
+, ejecuta 
+\begin_inset Formula $V$
+\end_inset
+
+ sobre 
+\begin_inset Formula $\langle w,c\rangle$
+\end_inset
+
+ y acepta o rechaza según lo haga 
+\begin_inset Formula $V$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+end{samepage}
+\end_layout
+
+\end_inset
+
+
+\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}$
+\end_inset
+
+, 
+\begin_inset Formula $L_{1}\cup L_{2},L_{1}\cap L_{2},L_{1}L_{2},L_{1}^{*}\in{\cal NP}$
+\end_inset
+
+.
+ Se desconoce si 
+\begin_inset Formula ${\cal NP}$
+\end_inset
+
+ es cerrada para el complemento o no.
+ 
+\begin_inset Formula ${\cal P}$
+\end_inset
+
+ y 
+\begin_inset Formula ${\cal NP}$
+\end_inset
+
+ no son cerradas para subconjuntos.
+\end_layout
+
+\begin_layout Standard
+\begin_inset Formula ${\cal P}\subseteq{\cal NP}$
+\end_inset
+
+, pero es un problema abierto si 
+\begin_inset Formula ${\cal P}={\cal NP}$
+\end_inset
+
+ o no.
+ La mayoría de investigadores consideran que 
+\begin_inset Formula ${\cal P}\neq{\cal NP}$
+\end_inset
+
+ porque se han invertido muchos recursos en encontrar algoritmos en tiempo
+ polinómico para ciertos problemas y no se han encontrado, y aunque se ha
+ intentado probar la existencia de algoritmos en 
+\begin_inset Formula ${\cal NP}$
+\end_inset
+
+ que no están en 
+\begin_inset Formula ${\cal P}$
+\end_inset
+
+, no se han invertido tantos recursos porque el incentivo económico de probar
+ algo que casi se da por hecho es relativamente bajo.
+\end_layout
+
+\begin_layout Standard
+Un problema tiene 
+\series bold
+tiempo pseudo-polinómico
+\series default
+ si su entrada es una cantidad fija de números y existe un algoritmo que
+ lo resuelve en tiempo polinómico respecto a estos números pero no respecto
+ a la longitud de la entrada.
+\end_layout
+
+\begin_layout Standard
+\begin_inset Formula $\text{PRIME}$
+\end_inset
+
+, el conjunto de números primos, es 
+\begin_inset Formula ${\cal NP}$
+\end_inset
+
+ y pseudo-polinómico, pues un algoritmo para decidir si 
+\begin_inset Formula $n\in\text{PRIME}$
+\end_inset
+
+ es comprobar si es divisible por algún número entre 2 y 
+\begin_inset Formula $n-1$
+\end_inset
+
+, haciendo 
+\begin_inset Formula $n-2$
+\end_inset
+
+ divisiones.
+ En 2002, los autores indios Agarwal, Kayal y Saxena encontraron un algoritmo
+ que decide 
+\begin_inset Formula $\text{PRIME}$
+\end_inset
+
+ en tiempo polinómico, el 
+\series bold
+\emph on
+\lang english
+AKS primality test
+\series default
+\emph default
+\lang spanish
+, probando que 
+\begin_inset Formula $\text{PRIME}\in{\cal P}$
+\end_inset
+
+.
+ Este algoritmo no es constructivo; no encuentra factores primos de un número
+ compuesto.
+\end_layout
+
+\end_body
+\end_document