NTIME (f) subconjunto de DSPACE (f)

Como a pergunta indica, como podemos provar que ? $\textbf{NTIME}(f(n)) \subseteq \textbf{DSPACE}(f(n))$

Alguém pode me indicar uma prova ou descrevê-la aqui? Obrigado!

complexity-theory time-complexity space-complexity gdiazc
fonte

Eu acho que existem mult. constantes escondidas lá. Você pode provar que . Apenas enumere todas as suposições não determinísticas possíveis do algoritmo e execute seu algoritmo com essas suposições. Aceite se uma das suposições levar a um estado de aceitação.

N T I M E (f (n)) \subseteq D S P A C E (2 \cdot f (n))

$NTIME(f(n)) \subseteq DSPACE(2\cdot f(n))$

Igor Shinkar 20/09/2013

Por que não fazer disso uma resposta?

Yuval Filmus

@IgorShinkar Existem vários resultados, como o teorema da velocidade linear e o teorema da compressão de fita, que dizem que você pode se livrar dessas constantes na "maioria" das circunstâncias. A aceleração linear diz que para qualquer ; a compactação de fita indica que , novamente para qualquer .

D T I M E (f (n)) \subseteq D T I M E (ϵ f (n) + n + 2)

$\mathrm{DTIME}(f(n)) \subseteq \mathrm{DTIME}(\epsilon f(n)+n+2)$

ϵ > 0

$\epsilon>0$

D S P A C E (f (n)) \subseteq D S P A C E (ϵ f (n) + O (1))

$\mathrm{DSPACE}(f(n))\subseteq \mathrm{DSPACE}(\epsilon f(n) + O(1))$

ϵ > 0

$\epsilon>0$

precisa saber é o seguinte

Respostas:

Aqui está uma versão expandida do comentário de Igor Shinkar. A maneira mais simples de simular uma máquina não determinística em execução no tempo e no espaço usa o espaço . Enumeramos sobre todos os lançamentos possíveis de moedas, simulando a máquina original em cada uma delas; isso requer espaço para armazenar os lançamentos de moedas espaço para simular a máquina real. Há uma pequena dificuldade aqui: quando os lançamentos de moedas são "lidos" pela máquina (original), precisamos marcar de alguma forma onde estamos na sequência dos lançamentos de moedas; podemos usar um bit adicional por sorteio. Provavelmente é possível otimizar isso ainda mais. $f(n)$ $s(n) \leq f(n)$ $s(n) + 2f(n) + O(1)$ $f(n)$ $s(n)$

Se tomarmos cuidado, poderemos conseguir algo ainda melhor, pois em cada execução do programa, o número total de lançamentos de moedas e o espaço total usado somam no máximo . Eu suspeito que é possível executar a simulação no espaço . Talvez tenhamos de assumir algo como para isso. $f(n)$ $(1+o(1))f(n)$ $f(n) = \Omega(\log n)$

Como Igor menciona, geralmente classes limitadas a recursos são definidas apenas "até o grande O", de modo que o resultado, que usa o espaço , ainda está em . $O(f(n))$ $\mathrm{DSPACE}(f(n))$

Yuval Filmus
fonte