¿Una separación explícita entre la constructibilidad en el tiempo y la constructibilidad en el espacio?

Muestre una función que sea construible en el espacio pero no construible en el tiempo. $f(n)$

¿Está este problema relacionado con una posible separación entre las clases de complejidad DTIME (f (n)) y SPACE (f (n))?

cc.complexity-theory space-bounded separation Tian Liu
fuente

en.wikipedia.org/wiki/Constructible_function Hasta donde yo sé, esta pregunta no está relacionada con TIME (f (n)) vs SPACE (f (n)), pero tenga en cuenta que estas dos clases son diferentes. Busque los artículos "On Time Versus Space", "On Time Versus Space II", "On Time Versus Space III"

Ryan Williams, del

Una observación rápida: creo que el problema es equivalente a preguntar si DTIME (f (n)) ∩TALLY y SPACE (f (n)) ∩TALLY pueden ser diferentes para alguna función construible en el espacio f (n), donde TALLY es la clase de idiomas que son subconjuntos de 1 ^ *.

Tsuyoshi Ito

Vaya, pueden no ser equivalentes. Aquí hay una prueba de una dirección. Si existe un idioma L = {1 ^ n | n∈S} ∈ TALLY∩ (ESPACIO (f (n)) ∖ DTIME (f (n))) para alguna función construible en el espacio f (n), entonces tanto f (n) como f (n) + χ_S (n ) (donde χ_S (n) es la función característica de S) son construibles en el espacio pero no ambos son construibles en el tiempo y, por lo tanto, al menos uno de ellos es una función construible en el espacio pero no construible en el tiempo.

Tsuyoshi Ito

Gracias a Ryan, por su comentario, sé que TIME (f (n)) está contenido en SPACE (f (n) / log f (n)) por Hopcroft et al, y este último está contenido adecuadamente en SPACE (f (n )) por el teorema de la jerarquía espacial.

Tian Liu

Gracias a Tsuyoshi, ideas muy inteligentes, si tanto f (n) como f (n) + χ_S (n) son construibles en el tiempo, entonces podemos decidir si n∈S en la mayoría de las veces f (n) +1 tiempo, entonces L ∈TALLY ∩ DTIME (f (n)), una contradicción. pero ¿pueden sus construcciones llamarse "explícitas"? ¿Cuál no es construible en el tiempo, f (n) o f (n) + χ_S (n)? por "explícito" si quiero decir que podemos decidir el valor f (n) para todo n, entonces su construcción es explícita.

Tian Liu

Respuestas:

Una función es construible en el tiempo si hay una máquina Turing que, en la entrada , calcula la función en el tiempo . $T \colon \mathbb{N} \to \mathbb{N}$ $M$ $1^n$ $x \mapsto T(|x|)$ $O(T(n))$

Una función es construible en el espacio si hay una máquina de Turing que, en la entrada , calcula la función en el espacio . $S \colon \mathbb{N} \to \mathbb{N}$ $M$ $1^n$ $x \mapsto S(|x|)$ $O(S(n))$

Algunos textos requieren que las funciones construibles tiempo / espacio no sean decrecientes. Algunos textos requieren que las funciones construibles en el tiempo satisfagan , y las funciones construibles en el espacio satisfacen . Algunos textos no hacen uso de la notación en la definición. $T(n)\ge n$ $S(n)\ge \log n$ $O(\cdot)$

De todos modos, es fácil demostrar que todos los "ordinarios" función , que satisface y se puede construir el espacio, pero no construible tiempo. $f$ $f(n)\ge \log n$ $f(n) = o(n)$

El problema de la constructibilidad no está directamente relacionado con la posible separación entre las clases de complejidad DTIME (f (n)) y SPACE (f (n)). Sin embargo, la declaración de los teoremas de la jerarquía del tiempo y el espacio incorpora la constructibilidad. Por ejemplo:

Teorema de la jerarquía de tiempo Si , son funciones construibles en el tiempo que satisfacen , entonces es un subconjunto apropiado de . $f$ $g$ $f(n)\log f(n) = o(g(n))$ $\mathbf{DTIME}(f(n))$ $\mathbf{DTIME}(g(n))$

Consulte el libro de Arora & Barak o el de Papadimitriou para obtener más información. (Este último usa el término "función de complejidad adecuada" para referirse a uno que es tanto tiempo como espacio construible).

MS Dousti
fuente

Gracias. Prefiero la definición de que una función es construible en tiempo / espacio si hay una máquina de Turing que se ejecuta exactamente en esos pasos / cuadrados de cinta. Por supuesto, según los teoremas de aceleración lineal del tiempo / espacio, esto es equivalente a sus definiciones / libro de texto.

Tian Liu

Sadeq, sus definiciones de "tiempo construible" y "espacio construible" son idénticas palabra por palabra. ¿Estás diciendo que estos son solo dos nombres diferentes para exactamente el mismo concepto? Si no, tal vez debería arreglar sus definiciones.

Yitz

Es solo un error tipográfico.

Tsuyoshi Ito

Lo siento, Yitz. Arreglé el error tipográfico.

MS Dousti

es construible en el espacio pero no en el tiempo. La razón es que puede asignar a la representación binaria en el espacio pero no en el tiempo . $f(n)=\log n$ $1^n$ $O(\log n)$ $O(\log n)$

Mohammad Al-Turkistany
fuente

Gracias al comentario y respuesta. Pero, ¿puedes mostrar una función f (n) que sea al menos lineal, es decir, f (n)> = n, para la separación? Parece que una función construible en el tiempo no puede ser menor que n por una razón aparente: tiene que leer todos los bits de entrada, de lo contrario, un argumento adverso puede mostrar que la función no se calcula correctamente.

Tian Liu

@Tian,

es una función construible en el espacio pero no en el tiempo.

f (n) = n

$f(n)= n$

Mohammad Al-Turkistany

Gracias de nuevo, pero ¿asume que el cabezal de lectura en la cinta de entrada se encuentra inicialmente a la izquierda del primer bit de entrada? en ese caso, para detectar el último bit de entrada, la cabeza tiene que moverse a la derecha n + 1 veces hasta encontrar el primer espacio en blanco después de la entrada. Entonces

es construible en el tiempo. Entonces, ¿puede dar una separación "no trival" mediante una función f (n)> = n + 1?

f (n) = n + 1

$f(n)=n+1$

Tian Liu

$EXP-TIME=EXP-SPACE$ $EXP-SPACE-COMPLETE$ $L\in EXP-SPACE$ $L\subseteq\{0,1\}^*$ $k\in\mathbb{N}$ $L$ $M$ $2^{n^k}$

f (n) = {\begin{cases} 8 n + 2 & if (first ⌊ \sqrt[k]{⌊ \log n ⌋ + 1} ⌋ bits of b i n (n)) \in L \\ 8 n + 1 & else \end{cases}

$f(n)=\left\{\begin{array}{ll} 8n+2 & \mbox{if }\left(\mbox{first } \lfloor\sqrt[k]{\lfloor\log n\rfloor+1}\rfloor\mbox{ bits of } bin(n)\right)\in L\\ 8n+1 & \mbox{else} \end{array} \right.$

$2n$ $f$ $f$ $L$

Esta respuesta usa la misma idea.

David G
fuente