Justificação do log f no teorema da hierarquia DTIME

Se olharmos para o teorema da hierarquia DTIME, temos um log devido à sobrecarga na simulação de uma máquina de Turing determinística por uma máquina universal:

$DTIME(\frac{f}{\log f}) \subsetneq DTIME(f)$

Não temos esse tipo de sobrecarga para o NTIME do DSPACE. Uma justificativa básica vem dos detalhes da prova, considerando a diferença entre os simuladores.

Minha pergunta é a seguinte: sem considerar os detalhes da prova do teorema da hierarquia DTIME, existe uma justificativa para esse log ou pode ser apenas uma consequência da prova e seria razoável imaginar que se $f = o(g)$ então

$DTIME(f) \subsetneq DTIME(g)$

Na minha opinião, considerando que a explicação da simulação é uma boa justificativa, ela deve ser justificada por provar que, se obtivéssemos um resultado melhor, poderíamos criar uma simulação melhor.

O teorema da hierarquia de tempo é o assunto do meu projeto de diploma, talvez você queira ver os comentários sobre minha pergunta Limites inferiores e separação de classes .

Olhando para trás para esta pergunta e como ela se relaciona com o que você está perguntando, tive uma idéia que pode mostrar que a sobrecarga da simulação de TM de fita única para fita única necessária para a prova do teorema não pode ser melhorada. Assim, é necessária outra abordagem se desejarmos melhorar esse resultado.

EDIT: Esta prova está incorreta; veja os comentários abaixo pelo motivo exato. Atualmente, estou editando a resposta para refletir isso.

$A$$\{ 0^{k}1^{k}| k \geq 0 \}$

$O(n \log n)$

$O(n)$

$o( T(n) \log T(n) )$$T(n)$$o( n \log n)$$A$$\log T(n)$ é o melhor que podemos fazer ao simular máquinas de fita múltipla com máquinas de fita única.

Sei que essa é uma afirmação forte, por isso posso estar errado na minha interpretação.

$NTIME$$SPACE$

$DTIME(n) \neq NTIME(n)$$P \neq NP$$DTIME(n^{k}) \neq NTIME(n)$$k$. Portanto, uma classe não determinística muito pequena é muito mais poderosa do que qualquer determinística. Portanto, dado o quão poderoso é o tempo não determinístico de um recurso, eu esperaria que uma quantidade maior de tempo determinístico fosse necessária para tornar uma MT mais poderosa para compensar o poder do não-determinismo.

$\lg$

$\lg$

Existem alguns motivos e argumentos para usar TMs de fita única para definir classes de complexidade de tempo, mas o uso de TMs de fita única para definir classes de complexidade não é universal, por exemplo, consulte Lance Fortnow e Rahul Santhanam [2007], onde eles usam fitas múltiplas. TMs.

A referência original para o teorema da hierarquia de tempo é Hennie e Stearns [1966]. Eles provam o teorema das máquinas com duas fitas. A Teoria Clássica da Recursão de Odifreddi cita-os e Hartmanis [1968] e descreve uma prova semelhante à do livro de Sipser.

$\Omega(n^2)$$o(n^2)$

1. $\lg$

2. Para o segundo caso, o artigo fornece diretamente um idioma para a separação e não usa simulação. Isso usa propriedades particulares de TMs de fita única com tempo de execução sub-quadrático.

$o(n^2)$

Como eu disse acima, a menos que você esteja comprometido com o modelo de fita única por algum motivo, mesmo quando o tempo é sub-quadrático, não há uma lacuna a ser preenchida, o teorema da hierarquia de tempo é o mais rígido possível.

PS: se estivermos usando TMs de fita múltipla, ou seja, uma máquina de Turing na classe pode ter um número fixo mas arbitrário de fitas, o resultado da Fürer não se aplica.

1. Martin Fürer, " A estreita hierarquia determinística do tempo ", 1982
2. Piergiorgio Odifreddi, "Teoria Clássica da Recursão", vol. II, 1999 (página 84)
3. Juris Hartmanis, " Complexidade Computacional de Computações com Máquina de Turing com Uma Fita ", 1968
4. FC Hennie e RE Stearns, " Simulação em Duas Fitas de Máquinas de Turing Multitape ", 1966
5. Artigo de Lance Fortnow e Rahul Santhanam " Hierarquias do tempo: uma pesquisa ", 2007

$\mathrm{Time}(o(f)) ⊊ \mathrm{Time}(O(f)$$f$

$\mathrm{DTime}(g) ⊊ \mathrm{DTime}(f)$$k$$k+1$$k$

$\mathrm{DTime}(o(f)) ⊊ \mathrm{DTime}(O(f))$

De fato, já temos o seguinte.

Teorema: Para todo e todo da forma ( e racional; ou ), .$ε>0$$f$$n^a (\log n)^b$$a$$b$$a>1$$a=1∧b≥0$$\mathrm{DTime}(O(f /(\log f)^ε) ⊊ \mathrm{DTime}(O(f))$

Prova: se todo idioma com um algoritmo de decisão puder ser decidido no tempo , preenchendo a entrada, todo idioma com um algoritmo de decisão pode ser decidido no tempo (onde é fixo ) e, assim, para cada constante , , contradizendo o teorema da hierarquia de tempo.$O(f)$$O(f / (\log f)^ε)$$O(f(n) (\log f(n))^{kε})$$O(f(n) \, (\log f(n))^{(k-1)ε})$$k≥0$$c≥0$$\mathrm{DTime}(O(f(n) (\log f(n))^c)) = \mathrm{DTime}(O(f(n)))$

No entanto, essa prova não construtiva tem três limitações:
* A prova exige que seja bem-comportado (não apenas construtível no tempo, mas também em certo sentido contínuo). * Não conhecemos um idioma específico que esteja em mas não em . Para um suficientemente grande , simulação de -tape máquinas Turing não é em , mas que não têm de excluir que, mesmo para e , o mínimo que é> BB (BB (1000)), onde BB é a função de castor ocupado. * Não sabemos que a inclusão é robusta.$f$
$\mathrm{DTime}(O(f))$$\mathrm{DTime}(O(f/(\log f)^ε)$$k$$k$$\mathrm{DTime}(O(f/(\log f)^ε)$$ε=1$$f(n)=n^2$$k$
$\mathrm{DTime}(O(f/(\log f)^ε)$ falhará em algumas entradas, mas não provamos que ele falhe em algumas entradas para todos, com exceção de muitos tamanhos de entrada finitos (embora seja muito surpreendente se não).