From eddd61b056d47adb0c99779545ac8e4b59a467b5 Mon Sep 17 00:00:00 2001
From: Juan Marin Noguera <juan@mnpi.eu>
Date: Wed, 5 Oct 2022 18:45:16 +0200
Subject: MC tema 8

---
 mc/n7.lyx | 45 +++++++++++++++++++++++++++++++++++++++++++--
 1 file changed, 43 insertions(+), 2 deletions(-)

(limited to 'mc/n7.lyx')

diff --git a/mc/n7.lyx b/mc/n7.lyx
index 9bfe853..c1791e0 100644
--- a/mc/n7.lyx
+++ b/mc/n7.lyx
@@ -154,6 +154,47 @@ Los problemas en esta clase se consideran tratables, y el resto intratables.
  y exponencial es útil en la práctica.
 \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
 
-- 
cgit v1.2.3