MC tema 8

1 files changed, 43 insertions, 2 deletions

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