É

Defina como a classe de idiomas que pode ser aceita por uma máquina de Turing (multitape) no tempo f ( n ) + 1 . (O " + 1 " é apenas para simplificar a notação e evitar confusão.) Observe que não há O ( ⋅ ) em torno de f ( n ) + 1 .$\mathsf{DTIME}(f(n))$$f(n) + 1$$+ 1$$O(\cdot)$$f(n) + 1$

É verdade que ?$\mathsf{DTIME}(n) = \mathsf{DTIME}(2n)$

Usando o teorema da aceleração linear , podemos provar , mas podemos alcançar n ?$\mathsf{DTIME}(2n) = \mathsf{DTIME}(1.01n)$$n$

Parece que a linguagem dos palíndromos está em ; para tópicos relacionados, consulte a publicação no blog de Lipton sobre algoritmos de string$\mathsf{DTIME}(n)$

Do comentário:

Em " Máquinas determinísticas de Turing na faixa entre tempo real e tempo linear ", descobri:

... se e r ′ ∈ o ( r ), então D T I M E ( n + r ′ ) ⊂ D T I M E ( n + r ) ...$r \in T^{−1}(DTM)$$r' \in o(r)$$DTIME(n+r') \subset DTIME(n+r)$