Siguiente: Jerarquía en espacio Un nivel arriba: Complejidades de tiempo y Anterior: Dispositivos de cómputo

Tiempos y espacios

Sea $M\in{\cal C}$ un dispositivo de cómputo. Para una entrada $\mbox{\bf x}=(x_1,\ldots,x_n)\in N^n$ definimos

• longitud de $\mbox{\bf x}$, $\mbox{\it long}(\mbox{\bf x})\approx \sum_{i=1}^n\log x_i.$
• tiempo de $\mbox{\bf x}$, $\mbox{\it tiem}_M(\mbox{\bf x})$ es el número de instrucciones ejecutadas hasta arribar a un estado final,
• espacio de $\mbox{\bf x}$, $\mbox{\it espa}_M(\mbox{\bf x})$ es el número de localidades de almacenamiento ocupadas hasta arribar a un estado final.

M determina a su vez dos funciones de tiempo y de espacio:

$$\begin{array}{lcl} \begin{array}[t]{rcl} t_M:N &\rightarrow... ...ert\mbox{\it long}(\mbox{\bf x})=n\}. \end{array} \end{array}$$

Para una clase de dispositivos de cómputo ${\cal C}$ y una función $f:R \rightarrow R$ definimos las clases de problemas siguientes:

$$\begin{eqnarray*}\mbox{\rm DTIME}_{{\cal C}}(f) &=& \{A\vert\exists M\in {\cal C... ...al C}: (M\mbox{\rm es comprobador de }A)\; \& s_M(n)=O(f(n))\} \end{eqnarray*}$$

Teorema 3.1   Para cualquier función computable f tenemos que existen sendos problemas A y B tales que $A\not \in \mbox{\rm DTIME}(f)$, y $B\not \in \mbox{\rm DSPACE}(f)$.

Así pues no hay límites computables para las clases de problemas. Demostración: Dada f, veamos tan solo la construcción de A. Sean $\left(M_i\right)_i$ y $\left(\mbox{\bf x}_i\right)_i$ sendas enumeraciones de los dispositivos de cómputo y de las posibles entradas. Sea

$$A=\{\mbox{\bf x}_i\vert M_i \mbox{\rm deja de reconocer a $\m... ...i$ en a lo sumo $f(\mbox{\it long}(\mbox{\bf x}_i))$ pasos.}\}.$$

A puede ser efectivamente reconocido utilizando la máquina universal en ${\cal C}$:

1.

Dado $\mbox{\bf x}$ se calcula i tal que $\mbox{\bf x}_i=\mbox{\bf x}$ y se calcula M_i también.

2.

Se calcula $t=f(\mbox{\it long}(\mbox{\bf x}_i))$.

3.

Se realiza el cálculo de $M_i(\mbox{\bf x}_i)$ llevando un recuento de la duración d de la ``corrida''.

4.

Si M_i reconoce a $\mbox{\bf x}$ y d > t entonces se acepta a $\mbox{\bf x}$. En otro caso se rechaza.

Supongamos que $A\in \mbox{\rm DTIME}(f)$. Entonces $\exists i_0:\;(M_{i_o}\mbox{\rm reconoce a }A) \;\&\;t_{M_{i_o}}=O(f).$ Tenemos por un lado que

$$\begin{eqnarray*}\mbox{\bf x}_{i_o}\in A &\Rightarrow& \mbox{\it tiem}_{M_{i_o}}... ...{\bf x}_{i_o})) \\ &\Rightarrow& A\not\in \mbox{\rm DTIME}(f) \end{eqnarray*}$$

y esto último contradice la suposición. Y por otro lado

$$\begin{eqnarray*}\mbox{\bf x}_{i_o}\not\in A &\Rightarrow& M_{i_o}\mbox{\rm no r... ... }\mbox{\bf x}_{i_o} \\ &\Rightarrow& \mbox{\bf x}_{i_o}\in A \end{eqnarray*}$$

lo cual también es una contradicción. q.e.d.
Siguiente: Jerarquía en espacio Un nivel arriba: Complejidades de tiempo y Anterior: Dispositivos de cómputo