Czy

Zdefiniuj jako klasę języków, które mogą być akceptowane przez (wielopasmową) maszynę Turinga w czasie f ( n ) + 1 . („ + 1 ” ma jedynie na celu uproszczenie notacji i uniknięcie pomyłek.) Zauważ, że nie ma O ( ⋅ ) wokół f ( n ) + 1 .$\mathsf{DTIME}(f(n))$$f(n) + 1$$+ 1$$O(\cdot)$$f(n) + 1$

Czy to prawda, że ?$\mathsf{DTIME}(n) = \mathsf{DTIME}(2n)$

Za pomocą twierdzenia o liniowym przyspieszeniu możemy udowodnić , ale czy możemy osiągnąć n ?$\mathsf{DTIME}(2n) = \mathsf{DTIME}(1.01n)$$n$

Wydaje się, że język palindromów jest w ; pokrewne tematy można znaleźć w blogu Liptona na temat algorytmów ciągów$\mathsf{DTIME}(n)$

Z komentarza:

W „ Deterministycznych maszynach Turinga w zakresie od czasu rzeczywistego do czasu liniowego ” znalazłem:

... jeśli i r ′ ∈ o ( r ), to 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)$