Compensación espacio-tiempo y el mejor algoritmo

Considere un lenguaje $L$ tal que:

$L \in DTIME(O(f(n))) \cap DSPACE(O(g(n)))$

y asi que

$L \not\in DTIME(o(f(n))) \cup DSPACE(o(g(n)))$

En otras palabras, la máquina más rápida calcula en el tiempo y la máquina más eficiente en espacio calcula mientras usa el espacio . $M$ $L$ $O(f(n))$ $M'$ $L$ $O(g(n))$

¿Qué se puede decir sobre la eficiencia espacial de M o la eficiencia temporal de M '? O más precisamente, si es el conjunto de todas las máquinas que calculan en , ¿qué podemos decir acerca de la máquina más eficiente en espacio en ? ¿Qué pasa con lo mismo para la versión espacial obvia: . $\mathbb{M}_T$ $L$ $O(f(n))$ $\mathbb{M}_T$ $\mathbb{M}_S$

Alternativamente, Can y ser usado para definir unas concesiones buen espacio-tiempo? ¿Bajo qué condiciones es o más generalmente para algún intercambio espacio-tiempo bajo qué condiciones es . $f(n)$ $g(n)$ $TS \in o(f(n)g(n))$ $h(T,S)$ $h(T,S) \in h(o(f(n)),o(g(n)))$

cc.complexity-theory ds.algorithms open-problem space-time-tradeoff Artem Kaznatcheev
fuente

¿Está preguntando por una L arbitraria o le interesan los resultados de esta naturaleza que podrían existir para problemas específicos?

Suresh Venkat

Estoy interesado en ambos, de verdad. Mi motivación original era principalmente de problemas de accesibilidad (conectividad st dirigida y no dirigida). Sin embargo, sería interesante saber si existen límites generales o técnicas disponibles.

Artem Kaznatcheev

Por lo tanto, tomar cualquier idioma decidable

. Este lenguaje da funciones

modo que

L

$L$

f_{L}, g_{L}

$f_L, g_L$

L \in TIME [f_{L} (n)] \cap SPACE [g_{L} (n)]

$L \in \text{TIME}[f_L(n)] \cap \text{SPACE}[g_L(n)]$

L \notin TIME [o (f_{L} (n))] \cup SPACE [o (g_{L} (n))]

$L \not\in \text{TIME}[o(f_L(n))] \cup \text{SPACE}[o(g_L(n))]$ . (¿Es esto cierto, o hay idiomas de "aceleración" que lo violan?)

Derrick Stolee

Específicamente, hay ejemplos en la búsqueda de rango de problemas que admiten (Consulta, Espacio) de la forma (log n, poly (n)), o (sublineal, lineal), o cualquier interpolación de los mismos

Suresh Venkat

¿Relacionado? Límites inferiores de espacio-tiempo

Tsuyoshi Ito

Respuestas:

El f y g prototípico aquí probablemente sería poli-tiempo y espacio polilog. El problema interesante aquí es la conectividad (en gráficos dirigidos) que se puede resolver en tiempo polinomial (usando espacio lineal) o en espacio polylog (usando tiempo superpolinomial). Es un problema abierto famoso si se puede resolver en TIME-SPACE (poly, polylog), una clase conocida como SC .

Es decir, su pregunta es un problema abierto bien conocido. No creo que se sepa nada no trivial aquí.

Noam
fuente

gracias por la respuesta. Sospechaba que sería un problema abierto, pero esperaba que algunos resultados específicos ya se conocieran. Desafortunado :(.

Artem Kaznatcheev

-4

esta pregunta apareció en "preguntas similares" cuando acabo de publicar esta otra pregunta /cstheory/9677/deterministic-time-space-separation-via-space-compression .

allí cito el resultado de 1977 de hopcroft, paul, valientes (aparentemente más conocido según rj lipton en su blog) que parece aplicarse a su pregunta, es decir, $\mathsf{DTIME}(t(n)) \subseteq \mathsf{DSPACE}(t(n)/log(n))$

vzn
fuente

No veo cómo esto se aplica a las compensaciones espacio-tiempo ...

Artem Kaznatcheev

El concepto de "compensación espacio-temporal" parece no estar exactamente definido. mi respuesta se puede entender de la siguiente manera: un programa que está en DTIME (t (n)) está "naturalmente" en DSPACE (t (n)). los resultados de HPV1977 le permiten a uno construir una TM, a expensas de algún aumento en los estados (¿y las cintas tal vez?) de modo que en su lugar se necesita espacio DSPACE (t (n) / log (n)). por lo tanto, una "compensación"

vzn

Existe una comprensión estándar de las compensaciones en CS que no es en absoluto lo que usted describe (lo que describe no es una compensación en absoluto, sino solo una relación estándar entre DTIME y DSPACE). Además, explícitamente explico lo que quiero en el intercambio espacio-tiempo en mi pregunta, por favor lea las preguntas cuidadosamente antes de intentar responderlas.

Artem Kaznatcheev

si su definición de compensaciones espacio-temporales arriba en su pregunta es estándar como usted dice, ¿está definida en alguna literatura?

vzn

Mirando por encima de su definición, parece intuitivamente plausible que tales f (n), g (n) existan para todos los lenguajes decidibles, pero que uno no tenga problemas incluso demostrando que tales f (n), g (n) necesariamente existen debido al teorema de aceleración blum ....?

vzn