diff options
Diffstat (limited to 'mc/n7.lyx')
| -rw-r--r-- | mc/n7.lyx | 45 |
1 files changed, 43 insertions, 2 deletions
@@ -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 |