NTIME (f) subconjunto de DSPACE (f)

9

Como a pergunta indica, como podemos provar que ?NTIME(f(n))DSPACE(f(n))

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

gdiazc
fonte
4
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. NTIME(f(n))DSPACE(2f(n))
Igor Shinkar 20/09/2013
11
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 . DTIME(f(n))DTIME(ϵf(n)+n+2)ϵ>0DSPACE(f(n))DSPACE(ϵf(n)+O(1))ϵ>0
precisa saber é o seguinte

Respostas:

4

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)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)=Ω(logn)

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))DSPACE(f(n))

Yuval Filmus
fonte