Apakah

Tentukan sebagai kelas bahasa yang dapat diterima oleh mesin Turing (multitape) dalam waktu . (" " hanya untuk menyederhanakan notasi dan menghindari kebingungan.) Perhatikan bahwa tidak ada sekitar . $\mathsf{DTIME}(f(n))$ $f(n) + 1$ $+ 1$ $O(\cdot)$ $f(n) + 1$

Apakah benar bahwa ? $\mathsf{DTIME}(n) = \mathsf{DTIME}(2n)$

Dengan menggunakan teorema percepatan linier , kita dapat membuktikan , tetapi dapatkah kita mencapai ? $\mathsf{DTIME}(2n) = \mathsf{DTIME}(1.01n)$ $n$

Tampaknya bahasa palindrom dalam ; untuk topik terkait, lihat posting blog Lipton tentang algoritma string $\mathsf{DTIME}(n)$

cc.complexity-theory time-complexity turing-machines time-hierarchy domotorp
sumber

Dalam " Deterministic Turing Machines dalam Rentang antara Real-Time dan Linear-Time " saya menemukan: jika

dan

maka

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

Bagus, sepertinya hanya apa yang saya cari. Apakah Anda ingin mengubahnya menjadi jawaban?

domotorp

pertanyaan yang menarik tetapi keberatan dengan definisi ulang kelas kompleksitas standar DTIME dengan cara yang tidak standar, menyarankan Anda setidaknya menyebutnya sesuatu seperti DTIME 'untuk menghindari kebingungan

vzn

Makalah ini mungkin membantu. [Rosenberg 67] Bahasa Yang Dapat Dibatasi

zZzZzZ

Jawaban:

Dari komentar:

Dalam " Deterministic Turing Machines dalam Rentang antara Real-Time dan Linear-Time " saya menemukan:

... jika dan maka ... $r \in T^{−1}(DTM)$ $r' \in o(r)$ $DTIME(n+r') \subset DTIME(n+r)$

Marzio De Biasi
sumber

Apa itu

T^{- 1} (D T M)

$T^{-1}(DTM)$

Emil Jeřábek

adalah kebalikan dari fungsi konstruk waktu yang meningkat dan tidak terbatas

(

kita memiliki

). Anda dapat menggantinya dengan fungsi sublinear yang jujur.

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