NTIME (f) subconjunto de DSPACE (f)

Como dice la pregunta, ¿cómo demostramos que ? $\textbf{NTIME}(f(n)) \subseteq \textbf{DSPACE}(f(n))$

¿Alguien puede señalarme una prueba o resumirla aquí? ¡Gracias!

complexity-theory time-complexity space-complexity gdiazc
fuente

Supongo que hay mult. constantes escondidas allí. Puede probar que

. Simplemente enumere todas las posibles suposiciones no deterministas del algoritmo y ejecute su algoritmo con estas suposiciones. Acepte si una de las conjeturas lleva a un estado de aceptación.

N T I M E (f (n)) \subseteq D S P A C E (2 \cdot f (n))

$NTIME(f(n)) \subseteq DSPACE(2\cdot f(n))$

Igor Shinkar

¿Por qué no hacer esto una respuesta?

Yuval Filmus

@IgorShinkar Hay varios resultados, como el teorema de aceleración lineal y el teorema de compresión de cinta que dicen que puede deshacerse de esas constantes en "la mayoría" de las circunstancias. La aceleración lineal dice que

para cualquier

; la compresión de cinta dice que

D T I M E (f (n)) \subseteq D T I M E (ϵ f (n) + n + 2)

$\mathrm{DTIME}(f(n)) \subseteq \mathrm{DTIME}(\epsilon f(n)+n+2)$

ϵ > 0

$\epsilon>0$

, nuevamente para cualquier

D S P A C E (f (n)) \subseteq D S P A C E (ϵ f (n) + O (1))

$\mathrm{DSPACE}(f(n))\subseteq \mathrm{DSPACE}(\epsilon f(n) + O(1))$

ϵ > 0

$\epsilon>0$

David Richerby

Respuestas:

Aquí hay una versión ampliada del comentario de Igor Shinkar. La forma más simple de simular una máquina no determinista que se ejecuta en el tiempo y el espacio utiliza espacio. Enumeramos todos los lanzamientos de monedas posibles, simulando la máquina original en cada uno de ellos; esto requiere espacio para almacenar los lanzamientos de monedas, y $f(n)$ $s(n) \leq f(n)$ $s(n) + 2f(n) + O(1)$ $f(n)$ espacio para simular la máquina real. Aquí hay una ligera dificultad: cuando los lanzamientos de monedas son "leídos" por la máquina (original), necesitamos marcar de alguna manera dónde estamos en la secuencia de lanzamientos de monedas; podemos usar un bit adicional por lanzamiento de moneda. Probablemente sea posible optimizar esto aún más. $s(n)$

Si tenemos cuidado, podríamos obtener algo aún mejor, ya que en cada ejecución del programa, el número total de lanzamientos de monedas y el espacio total utilizado se suman como máximo . Sospecho que es posible ejecutar la simulación en el espacio . Tal vez tendremos que asumir algo como para eso. $f(n)$ $(1+o(1))f(n)$ $f(n) = \Omega(\log n)$

Como menciona Igor, por lo general, las clases limitadas por recursos solo se definen "hasta O grande", de modo que el resultado, que usa el espacio , todavía está en . $O(f(n))$ $\mathrm{DSPACE}(f(n))$

Yuval Filmus
fuente