Jerarquías de tiempo en DSPACE (O (s (n)))

El teorema de la jerarquía del tiempo establece que las máquinas de Turing pueden resolver más problemas si tienen (suficiente) más tiempo. ¿Se mantiene de alguna manera si el espacio está limitado asintóticamente? ¿Cómo se relaciona $\textrm{DTISP}(g(n), O(s(n)))$ con $\textrm{DTISP}(f(n), O(s(n)))$ si $\frac{f}{g}$ crece lo suficientemente rápido?

Estoy especialmente interesado en el caso que $s(n) = n$ , $g(n) = n^3$ y $f(n) = 2^n$ .

En particular, consideraba el siguiente lenguaje: $L_k := \{ (\langle M \rangle, w) \; : \; \text{M rejects } (\langle M \rangle, w) \text{ using at most } |\langle M \rangle, w|^3 \text{ time steps},$ $k * |\langle M \rangle, w| \text{ cells and four different tape symbols} \}$

Sin embargo, $L_k$ podría decidirse en $n^3$ pasos utilizando $(k+1)n \in O(n)$ espacio.

Sin limitar $M$ a cuatro símbolos de cinta y permitir así comprimir celdas $O(n)$ en $n$ celdas, obtenemos problemas de espacio al simular una $M$ con demasiados símbolos de cinta. En este caso, el idioma ya no está en $\text{DSPACE}(O(n))$ . Lo mismo sucede cuando se configura $k = h(|w|)$ para algunas $h$ que se pueden calcular lo suficientemente rápido.

Esta pregunta es básicamente una reformulación de mi pregunta aquí .

Editar resumen: modificado ( s ( n ) ) ∩ DTIME ( f ( n ) ) a DTISP ( f ( n ) , s ( n ) ) , sin embargo, creo que vale la pena pensar en la intersección.$\textrm{DSPACE}(s(n)) \cap \textrm{DTIME}(f(n))$$\textrm{DTISP}(f(n), s(n))$

$\mathrm{DTISP}(O(n \log n),O(n)) = \mathrm{DSPACE}(O(n))$$\mathrm{NSPACE}(O(n))$$\mathrm{DTIME}(O(n))⊆\mathrm{DSPACE}(O(n/\log n))$

$ε>0$$O(2^{n-ε})$$\mathrm{DTISP}(O(f),O(s(n))) ⊊ \mathrm{DTISP}(O(f^{1+ε}),O(s(n)))$
$f(n)≥n$$f(n)$$2^{o(\min(n,s(n)))}$$f$

En particular (bajo la hipótesis), la existencia de una asignación satisfactoria para circuitos con entradas y tamaño sirve como contraejemplo a la igualdad de las clases.$⌊\mathrm{lg}(f^{1+ε/2})⌋$$(\log f)^{O(1)}$

Notas:

• CIRCUIT-SAT es al menos tan duro como -SAT (que se usa en la hipótesis del tiempo exponencial fuerte).$k$

• Por convención, en CIRCUIT-SAT, es el número de cables de entrada; el tamaño del circuito es .$n$$n^{O(1)}$

• Si la suposición utiliza CIRCUIT-SAT para tamaños de circuito cuasilineales, entonces el límite en se puede relajar a . Además, los supuestos más débiles / más fuertes sobre la dureza de CIRCUIT-SAT dan jerarquías más débiles / más fuertes (que podemos probar actualmente).$f(n)$$O((2-ε)^{\min(n,s(n))})$

• io significa infinitamente a menudo, y puede descartarse para que son continuas en cierto sentido (incluyendo ).$f$$f(n)=n^a$

• Parece probable que la jerarquía DTISP sea lo suficientemente nítida para distinguir de (y tal vez ) (cuando no es demasiado grande en relación con el espacio permitido).$O(f)$$o(f/\log f)$$o(f)$$f$

• Para distinguir de , solo necesitamos el supuesto más débil P ≠ PSPACE.$n^a$$2^n$