Separando as classes horárias

Um aluno meu fez recentemente a seguinte pergunta:

Provavelmente, isso pode ser demonstrado verdadeiro ao construir um $h(n)$ se $f,g$ forem construtíveis no tempo. Mas, em geral, acho que isso deve ser falso semelhante ao $DSPACE(o(\log(\log(n)))) = DSPACE(1)$ .

Se é definido como a classe de todos os idiomas decidíveis no tempo por uma máquina de Turing com duas fitas, suspeito que a resposta seja não. Em outras palavras, acho que nem sempre existe uma classe de complexidade de tempo estritamente intermediária.D T I M E ( f ( n ) ) O ( f ( n ) $DTIME(f(n))$$O(f(n))$

Nota: Essa resposta pode não ser exatamente o que você está procurando, porque estou considerando funções não computáveis ​​e não incluo todos os detalhes do argumento. Mas senti que é um bom começo. Por favor, sinta-se livre para fazer qualquer pergunta. Talvez eu possa preencher esses detalhes ainda mais em algum momento ou talvez isso leve a uma resposta melhor de um leitor interessado.

Considere funções no formato . Nós nos referimos a essas funções como funções numéricas naturais.$f : \mathbb{N} \rightarrow \mathbb{N}$

Reivindicação 1: afirmo que podemos construir uma função de número natural não decrescente de crescimento muito lento (não computável) modo que:$\varepsilon(n)$

(1) não diminui$\varepsilon(n)$

(2)$\varepsilon(n) = \omega(1)$

(3) Para todos os computáveis ​​ilimitados , o conjunto é infinito.$f: \mathbb{N} \rightarrow \mathbb{N}$$\{ n \; \vert \; \varepsilon(n) \leq f(n) \}$

Construímos ε ( n ) como uma função de passo não decrescente de crescimento lento. Vamos enumerar todas as funções computáveis ilimitados { f i } i ∈ N . Queremos construir ε ( n ) de tal maneira que para todo i e todo j ≤ i , m i n { $\varepsilon(n)$$\{ f_i \}_{i \in \mathbb{N}}$$\varepsilon(n)$$i$$j \leq i$|ε ( k ) ≥ i } ≥ m i n { k|f j ( k ) ≥ i } . Em outras palavras, esperamos mapear ε ( n ) para i até que as primeirasfunções i na enumeração sejam mapeadas para um valor maior ou igual a i pelo menos uma vez. Então, ε ( n ) continua sendomapeadopara i até que as primeirasfunções i + 1 na enumeração sejam mapeadas para um valor maior ou igual a i + 1 pelo menos uma vez e, nesse ponto, ele começaa ser mapeadopara i + $min\{ k \; \vert \; \varepsilon(k) \geq i\} \geq min\{ k \; \vert \; f_{j}(k) \geq i \}$$\varepsilon(n)$$i$$i$$i$$\varepsilon(n)$$i$$i+1$$i+1$$i+1$. Se continuarmos esse processo iterativo para construir ε ( n ) , então para qualquer função computável ilimitada, embora ε ( n ) nem sempre seja menor, ele será infinitamente menor que o mínimo.$\varepsilon(n)$$\varepsilon(n)$

Nota: acabei de fornecer alguma intuição por trás da reivindicação 1, não forneci uma prova detalhada. Sinta-se livre para participar da discussão abaixo.

Como ε ( n ) é uma função de crescimento lento, temos o seguinte:$\varepsilon(n)$

Acordo com a reivindicação 2: Para todas as funções calculáveis número natural de f ( n ) e h ( n ) , se H ( n ) = Ω ( f ( n $f(n)$$h(n)$ε ( n ) )eh(n)=O(f(n)), entãoh(n)=Θ(f(n)).$h(n) = \Omega(\frac{f(n)}{\varepsilon(n)})$$h(n) = O(f(n))$$h(n) = \Theta(f(n))$

Para a reivindicação 2, se existir uma função computável h ( n ) entre f ( n $h(n)$ε ( n ) ef(n)de tal modo queH(n)≠q(f(n)), em seguida, seríamos capazes de calcular uma função de número natural ilimitado que cresce mais do que slowelyε(n), que não é possível . $\frac{f(n)}{\varepsilon(n)}$$f(n)$$h(n) \neq \Theta(f(n))$$\varepsilon(n)$

Deixe-me explicar alguns detalhes relevantes. Suponha, por uma questão de contradição, que tal função h ( n ) exista. Então, ⌊ f ( n $h(n)$h ( n ) ⌋é ilimitado.$\lfloor \frac{f(n)}{h(n)} \rfloor$

Nota: A função anterior é calculável porque f ( n ) e h ( n ) são calculáveis.$f(n)$$h(n)$

Como h ( n ) = Ω ( f ( n )ε ( n ) ), temos⌊f(n$h(n) = \Omega(\frac{f(n)}{\varepsilon(n)})$h ( n ) ⌋=O(ε(n)). Segue-se que existe uma constanteαtal que para todonsuficientemente grande,⌊αf(n$\lfloor \frac{f(n)}{h(n)} \rfloor = O(\varepsilon(n))$$\alpha$$n$h ( n ) ⌋<ε(n). Como essa função é ilimitada e computável, podemos aplicar a Reivindicação 1 para obter queε(n)≤⌊αf(n$\lfloor \alpha \frac{f(n)}{h(n)} \rfloor < \varepsilon(n)$h ( n ) ⌋infinitamente frequentemente que contradiz a afirmação anterior.$\varepsilon(n) \leq \lfloor \alpha \frac{f(n)}{h(n)} \rfloor$

Reivindicação 3: Para uma função construtível no tempo f ( n ) , temos que D T I M E ( f ( n $f(n)$ε ( n ) )⊊DTIME(f(n)), aindanãoexisteh(n)tal quef(n$DTIME(\frac{f(n)}{\varepsilon(n)}) \subsetneq DTIME(f(n))$$h(n)$ε ( n ) ≤h(n)≤f(n)eDTIME(f(n$\frac{f(n)}{\varepsilon(n)} \leq h(n) \leq f(n)$ε ( n ) )⊊DTIME(H(n))⊊DTIME(f(n)).$DTIME(\frac{f(n)}{\varepsilon(n)}) \subsetneq DTIME(h(n)) \subsetneq DTIME(f(n))$

Para mostrar isso, D T I M E ( f ( n )ε ( n ) )⊊DTIME(f(n))é preciso utilizar uma hierarquia teorema vez mais forte e isto é onde usamos o pressuposto de que o número de fitas é fixo (que as referidas duas fitas acima). Veja "A estreita hierarquia determinística do tempo", de Martin Furer.$DTIME(\frac{f(n)}{\varepsilon(n)}) \subsetneq DTIME(f(n))$

Como não há funções numéricas naturais computáveis ​​entre f ( n )ε ( n ) ef(n)que não sejam os que estãoΘ(f(n)), tem-se que para cada funçãoh(n)de modo a quef(n$\frac{f(n)}{\varepsilon(n)}$$f(n)$$\Theta(f(n))$$h(n)$ε ( n ) ≤h(n)≤f(n)eh(n)≠q(f(n)),DTIME(f(n$\frac{f(n)}{\varepsilon(n)} \leq h(n) \leq f(n)$$h(n) \neq \Theta(f(n))$ε ( n ) )=DTIME(H(n)).$DTIME(\frac{f(n)}{\varepsilon(n)}) = DTIME(h(n))$

If this result is true, it would strengthen the best-known deterministic time hierarchy theorem. [This is more of a comment than an answer, but too long for a comment. It leaves open the direct construction of a counterexample.] Recall that the best Deterministic Time Hierarchy Theorem we currently have is that if $f(n), g(n)$ are time-constructible, and $g(n) \leq o( f(n) / \log f(n) )$, then $\mathsf{DTIME}(g(n)) \subsetneq \mathsf{DTIME}(f(n))$.

Now suppose your desired result is true, and let $g(n)$ be a time-constructible function that is close to, but still little-oh of, $f(n) / \log(f(n))$, say, $g(n) = f(n) / (\log f(n))^{3/2}$. (This $g$ may not be time-constructible for arbitrary time-constructible $f$, but surely for many time-constructible $f$ this $g$ is also time-constructible.) Now, your desired result produces an $h$ such that $\mathsf{DTIME}(g(n)) \subsetneq \mathsf{DTIME}(h(n)) \subsetneq \mathsf{DTIME}(f(n))$. In order to avoid improving the current-best time hierarchy theorem, we would need both $g(n) = o( h(n) / \log(h(n)) )$ and $h(n) = o(f(n) / \log(f(n))$. These two together imply that $g(n) \leq o( f(n) / (\log(f(n)) \log(h(n)))$. Since $h(n) \geq g(n)$, we have $g(n) \leq o( \frac{f(n)}{\log(f(n)) \log(g(n))})$, or equivalently $g(n) \log g(n) \leq o(f(n) / \log(f(n)))$. But $g(n) \log(g(n)) = f(n) / (\log(f(n))^{3/2} [\log(f(n)) - (3/2) \log \log(f(n)] \sim f(n) / \sqrt{\log(f(n))}$, which is not $o(f(n) / \log(f(n))$.

I think such a behaviour is true for 1-Tape-DTMs. On the one hand, we have $\mathrm{DTIME}_1(O(n)) = \mathrm{DTIME}_1(o(n \log n))$. Unfortunately, the only reference I know is in German: R. Reischuk, Einführung in die Komplexitätstheorie, Teubner, 1990, Theorem 3.1.8.

On the other hand, it should be possible to separate $\mathrm{DTIME}_1(O(n))$ and $\mathrm{DTIME}_1(O(n \log n))$ by the language $\{ x \#^{2^{|x|}} x \mid x \in \{0,1\}^* \}$ using a standard crossing sequence argument.