¿DSPACE (n) = DSPACE (1.5n)?

Desde el teorema de la jerarquía espacial se sabe que si $f$ es construible en el espacio, entonces DSPACE ( $2f(n)$ ) no es igual a DSPACE ( $f(n))$ .

Aquí, por DSPACE ( $f(n))$ me refiero a la clase de todos los problemas que se pueden resolver en el espacio $f(n)$ por una máquina de Turing con un alfabeto fijo. Esto permite considerar el teorema de la jerarquía espacial con tanta precisión.

El argumento estándar da la constante multiplicativa $2$ : necesitamos espacio $f(n)$ para construir un cálculo de alguna máquina de Turing por una universal. También necesitamos $f(n)$ para resolver un problema con la detención.

Pregunta: ¿ DSPACE ( $f(n)$ ) es igual a DSPACE ( $\frac{3}{2}f(n)$)?

Se puede demostrar que DSPACE $(f(\frac 32 n))\ne$ DSPACE$(f(n))$si$f$crece al menos linealmente usando una variante simple del argumento de relleno estándar. Para un lenguaje$L$, deje$L'=\{x0^{|x|/2}\mid x\in L\}$.

Reclamación. $L\in$ DSPACE $(f(n))$ si y solo si $L'\in$ DSPACE $(f(\frac 23n))$si$f(n)\ge \frac 32n$.

(Mi primera respuesta tuvo varias declaraciones incorrectas, gracias a Emil por detectar esto).

Primero mostraré cómo usar el reclamo para probar la jerarquía. Como $f$ crece al menos linealmente, tenemos DSPACE $(2f(n))\subset$ DSPACE $(f(2n))$ . Tome un idioma $L\in$ DSPACE $(f(2n))\setminus$ DSPACE $(f(n))$ . Usando el reclamo, $L'\in$ DSPACE $(f(\frac 43 n))=$ DSPACE$(f(n))$, donde la última igualdad es por suposición indirecta. Pero entonces$L\in$DSPACE$(f(\frac 32 n))=$ DSPACE$(f(n))$, donde la última igualdad es nuevamente por la suposición indirecta, dando una contradicción.

Prueba de la reclamación. Si $L'\in$ DSPACE $(f(\frac 23 n))$$L\in$$(f(n))$$|x|/2$$x$$L'$$f(n)\ge \frac 32 n$$f$$x$

$L'$$L'=\{x10^{|x|/2}\mid x\in L\}$$x10^{|x|/2}$$f$$x10^{|x|/2}$$f$