$ NSpace (s (n)) \ subseteq dspace (s (n)) $ if $ s (n) $ é construtível de tempo?

Question

Eu li do Teorema de Savitch que deu uma função totalmente construtível de espaço $ s (n) $ , temos

$$ NSpace (s (n)) \ subseteq dspace (s (n) ^ 2) $$

Estou querendo saber, o que acontece se $ s (n) $ é totalmente construtível em tempo, poderíamos ter o resultado da matemática do resultado mais forte $ NSpace (s (n)) \ subseteq dspace (s (n)) $ ? ...

Por exemplo, para totalmente construtível time-construtível $ s (n)) $ , temos o resultado:

$$ Nspace (s (n)) \ subseteq \ bigcock dtime (c ^ {s (n)} \ text {para} c \ geq 1 $$

No entanto, também temos:

$$ \ BigCop DTime (c ^ {s (n)} \ subseteq NTime (s (n)) \ subseteq dspace (s (n)) $$

Sempre que a primeira contenção segue-se de uma forma que, para uma base plenamente construtível $ s (n) $ , temos que $ c ^ {s (n)} $ pode ser 'simulado' pelos ramos não determinisitc de uma $ NTime $ máquina ..

Combinando as duas declarações acima, temos:

$$ NSpace (s (n)) \ subseteq dspace (s (n)) $$

para totalmente construtível $ s (n)) $ ... mas esse resultado é correto ou estou perdendo alguma coisa?

Answer 1

Constructibilidade de espaço é um arenque vermelho.O problema real em seu argumento é o passo $$ \ mathsf {dtime} (c ^ {s (n)} \ subseteq \ mathsf {ntime} (s (n)), $$ que não é esperado para manter em geral.Por exemplo, o problema de decidir se uma máquina de Turing de entrada pára no tempo $ 2 ^ n $ pode ser resolvido em tempo exponencial determinístico, mas é conjetado para não ser solucionável em não-detetistaTempo polinomial.

Além disso, embora não esteja claro se o Teorema de Savitch é apertado, espera-se que em geral $ \ mathsf {dspace} (s (n)) \ neq \ mathsf {nspace}(s (n)) $ .Por exemplo, acredita-se que $ \ mathsf {l} \ neq \ mathsf {nl} $ .