Troca espaço-tempo e o melhor algoritmo

Considere alguma linguagem tal que: $L$

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

e para que

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

Em outras palavras, a máquina mais rápida calcula no tempo e a máquina mais eficiente em espaço calcula enquanto usa o espaço . $M$ $L$ $O(f(n))$ $M'$ $L$ $O(g(n))$

O que se pode dizer sobre a eficiência espacial de M ou a eficiência temporal de M '? Ou, mais precisamente, se é o conjunto de todas as máquinas que compute em , então o que podemos dizer sobre a máquina eficiente espaço mais em ? O que sobre a mesma coisa para a versão espaço óbvia: . $\mathbb{M}_T$ $L$ $O(f(n))$ $\mathbb{M}_T$ $\mathbb{M}_S$

Alternativamente, Can e ser utilizado para definir algumas desvantagens bom espaço de tempo? Em que condições é ou mais geralmente para alguma troca no espaço-tempo sob quais condiçõ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
fonte

Você está perguntando sobre um L arbitrário ou está interessado em resultados dessa natureza que possam existir para problemas específicos?

Suresh Venkat

Estou interessado em ambos, realmente. Minha motivação original era principalmente de problemas de acessibilidade (conectividade st direcionada e não direcionada). No entanto, seria interessante saber se existem limites ou técnicas gerais disponíveis.

Artem Kaznatcheev

Portanto, tome qualquer linguagem decidível

. Este idioma fornece as funções

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))]$ . (Isso é verdade ou existem linguagens de "aceleração" que a violam?)

Derrick Stolee

Especificamente, existem exemplos na pesquisa por intervalo de problemas que admitem (Consulta, Espaço) da forma (log n, poli (n)) ou (sublinear, linear) ou qualquer interpolação do mesmo

Suresh Venkat

Relacionado? Limites inferiores da troca espaço-tempo

Tsuyoshi Ito 27/01

Respostas:

O protótipo tipicamente aqui seria provavelmente o tempo poli e o tempo polilog. O problema interessante aqui é a conectividade (em gráficos direcionados) que pode ser resolvida no tempo polinomial (usando espaço linear) ou no espaço polilogico (usando tempo super-polinomial). É um famoso problema aberto se pode ser resolvido no TIME-SPACE (poli, polilog), uma classe conhecida como SC .

Ou seja, sua pergunta é um problema em aberto bem conhecido. Não acho que algo não trivial seja conhecido aqui.

Noam
fonte

obrigado pela resposta. Eu suspeitava que seria um problema em aberto, mas esperava que alguns resultados específicos já fossem conhecidos. Lamentável :(.

Artem Kaznatcheev

-4

essa pergunta apareceu em "perguntas semelhantes" quando eu acabei de postar outra pergunta /cstheory/9677/deterministic-time-space-separation-via-space-compression .

cito lá hopcroft, paul, valiants resultado de 1977 (aparentemente mais conhecido de acordo com rj lipton em seu blog) que parece se aplicar à sua pergunta, ou seja, $\mathsf{DTIME}(t(n)) \subseteq \mathsf{DSPACE}(t(n)/log(n))$

vzn
fonte

Eu não vejo como isso se aplica ao tempo-espaço trade-offs ...

Artem Kaznatcheev

o conceito de "troca de espaço no tempo" parece não estar exatamente definido. minha resposta pode ser entendida da seguinte forma: um programa que está em DTIME (t (n)) é "naturalmente" em DSPACE (t (n)). os resultados do HPV1977 permitem construir uma TM, às custas de algum aumento nos estados (e fitas, talvez?), de modo que ocupe espaço DSPACE (t (n) / log (n)). portanto, uma "troca"

vzn 13/01/12

Existe um entendimento padrão das compensações no CS, que não é de todo o que você descreve (o que você descreve não é de todo, mas apenas um relacionamento padrão entre DTIME e DSPACE). Além disso, explico explicitamente o que quero na troca de tempo e espaço na minha pergunta. Por favor, leia as perguntas cuidadosamente antes de tentar respondê-las.

Artem Kaznatcheev

se sua definição de trocas no espaço-tempo acima em sua pergunta é padrão como você diz, está definida em alguma literatura?

vzn

examinando sua definição, parece intuitivamente plausível que tais f (n), g (n) existam para todas as linguagens decidíveis, mas não haveria problemas nem mesmo provando que tais f (n), g (n) necessariamente existem devido ao teorema do blum speedup ....?

vzn