Czy

Zdefiniuj jako klasę języków, które mogą być akceptowane przez (wielopasmową) maszynę Turinga w czasie . („ ” ma jedynie na celu uproszczenie notacji i uniknięcie pomyłek.) Zauważ, że nie ma wokół . $\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ąć ? $\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)$

— domotorp
źródło

W " deterministycznych Turinga maszyny w zakresie pomiędzy w czasie rzeczywistym i liniowo czas " I znaleziono: jeśli

, a

wówczas

r \in T^{- 1} (D T M)

$r \in T^{-1}(DTM)$

r^{'} \in o (r)

$r'\in o(r)$

D T I M E (n + r^{'}) \subset D T I M E (n + r)

$DTIME(n + r') \subset DTIME(n + r)$

— Marzio De Biasi

Fajnie, wydaje się, że właśnie tego szukałem. Czy chcesz przekonwertować to na odpowiedź?

— domotorp

ciekawe pytanie, ale sprzeciwiają się redefinicji standardowej klasy złożoności DTIME w niestandardowy sposób, sugerują przynajmniej nazwać to czymś takim jak DTIME ', aby uniknąć nieporozumień

— vzn

Ten artykuł może być pomocny. [Rosenberg 67] Języki definiowane w czasie rzeczywistym dl.acm.org/citation.cfm?id=321423

— zZzZzZ

Z komentarza:

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

... jeśli i to ... $r \in T^{−1}(DTM)$ $r' \in o(r)$ $DTIME(n+r') \subset DTIME(n+r)$

— Marzio De Biasi
źródło

Co to jest

T^{- 1} (D T M)

$T^{-1}(DTM)$

— Emil Jeřábek

jest odwrotnością rosnącej, nieograniczonej funkcji konstruowanej w czasie

(

mamy

). Możesz go zastąpić uczciwą funkcją podliniową.

T^{- 1} (D T M)

$T^{-1}(DTM)$

f

$f$

\forall c \in N, \exists n_{0}, c^{'} \in N

$\forall c \in \mathbb{N}, \exists n_0, c' \in \mathbb{N}$

\forall n \geq n_{0}

$\forall n \geq n_0$

c f (n) \leq f (c^{'} n)

$c f(n) \leq f(c'n)$

— Marzio De Biasi