O que acontece se melhorarmos os teoremas da hierarquia de tempo?

10

f,gf(n)logf(n)=o(g(n))f , g f ( n + 1 ) = o ( g ( n ) )

DTIME(f(n))DTIME(g(n))
f,gf(n+1)=o(g(n))é
NTIME(f(n))NTIME(g(n)).
Existem muitos resultados (antigos e atuais) que usam os teoremas da hierarquia de tempo para provar limites mais baixos. Aqui estão as minhas perguntas:
  • O que acontece se pudermos provar um resultado melhor para o caso determinístico ou não determinístico?

  • Se pudermos provar que existe uma lacuna entre a hierarquia de tempo determinística e a hierarquia de tempo não determinística, isso implica PNP ?

Marc Bury
fonte
Apenas uma pequena nota. Para k-tape máquinas de Turing com k>2 , o tempo de hierarquia teorema pode ser melhorada: cstheory.stackexchange.com/questions/5297/...
Michael Wehar

Respostas:

4

Sobre sua segunda pergunta. Não, isso não implicaria PNP . Os teoremas da hierarquia são principalmente úteis para determinar a quantidade de um único recurso necessário para uma TM, para que problemas adicionais possam ser resolvidos.

Por exemplo, sabemos que . Deixe- , , de modo a que e .f ( n ) = n g ( n ) h ( n ) f ( n + 1 ) = o ( g ( n ) ) f ( n ) l o g ( f ( n ) ) = o (DTIME(n)NTIME(n)f(n)=ng(n)h(n)f(n+1)=o(g(n))f(n)log(f(n))=o(h(n))

Dos teoremas da hierarquia, segue-se que e . Sob essas suposições, é possível .N T I M E ( f ( n ) ) N T I M E ( h ( n ) ) N T I M E ( g ( n ) ) D T IDTIME(f(n))DTIME(g(n))NTIME(f(n))NTIME(h(n))NTIME(g(n))DTIME(h(n))

Os teoremas da hierarquia podem ser usados ​​para determinar as relações entre os recursos, dada uma igualdade entre eles. Por exemplo, suponha que . Sabemos que , para tal que , não pode ser igual a , devido ao teorema da hierarquia NTIME.N T I M E ( g ( n ) ) g ( n ) 2 n + 1 = o ( g ( n ) ) S P A C E ( n )NTIME(2n)=SPACE(n)NTIME(g(n))g(n)2n+1=o(g(n))SPACE(n)

chazisop
fonte
11
Não vejo por que uma lacuna não poderia implicar . É claro que não é uma implicação direta da lacuna, mas talvez haja outra implicação intermediária que a implique. PNP
Marc Bury
0

a hierarquia thms também trata de um continuum no tempo e no espaço (considerado separadamente) e parece possível que o continuum não seja mais "granular" do que está implícito nos teoremas, ou seja, eles podem ser a melhor "granularidade" possível.

sua segunda pergunta não parece clara ou talvez não esteja bem definida, a menos que você possa definir melhor o que quer dizer com "lacuna". todos os problemas decidíveis são solucionáveis ​​em algum lugar das duas hierarquias. a dificuldade é determinar as inter-relações. uma das raras "lacunas" ou separações na teoria atual foi de fato comprovada em tempo determinístico versus tempo não determinístico, de modo que [1]. veja também [2] para uma pergunta semelhante e avanços "recentes"DTIME(n)NTIME(n)

[1] PPST1983 http://dl.acm.org/citation.cfm?id=1382850

[2] NTIME (n ^ k) TI DTIME (n ^ k)?

vzn
fonte