Est ?

Définissez comme la classe de langues pouvant être acceptée par une machine de Turing (multitape) dans le temps . (Le " " est juste pour simplifier la notation et éviter toute confusion.) Notez qu'il n'y a pas de autour de . $\mathsf{DTIME}(f(n))$ $f(n) + 1$ $+ 1$ $O(\cdot)$ $f(n) + 1$

Est-il vrai que ? $\mathsf{DTIME}(n) = \mathsf{DTIME}(2n)$

En utilisant le théorème d'accélération linéaire , nous pouvons prouver , mais pouvons-nous atteindre ? $\mathsf{DTIME}(2n) = \mathsf{DTIME}(1.01n)$ $n$

Il semble que le langage des palindromes soit dans ; pour des sujets connexes, voir le blog de Lipton sur les algorithmes de chaîne $\mathsf{DTIME}(n)$

cc.complexity-theory time-complexity turing-machines time-hierarchy domotorp
la source

Dans " Machines de Turing déterministes dans la plage entre temps réel et temps linéaire ", j'ai trouvé: si and then

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

Nice, semble être exactement ce que je cherchais. Voulez-vous le convertir en réponse?

domotorp

question intéressante mais objectez à la redéfinition d'une classe de complexité standard DTIME d'une manière non standard, suggérez-vous au moins de l'appeler quelque chose comme DTIME 'pour éviter toute confusion

vzn

Ce document peut être utile. [Rosenberg 67] Langues définissables en temps réel dl.acm.org/citation.cfm?id=321423

zZzZzZ

Réponses:

Du commentaire:

Dans " Machines de Turing déterministes dans la plage entre temps réel et temps linéaire ", j'ai trouvé:

... si and then ... $r \in T^{−1}(DTM)$ $r' \in o(r)$ $DTIME(n+r') \subset DTIME(n+r)$

Marzio De Biasi
la source

Qu'est-ce que

T^{- 1} (D T M)

$T^{-1}(DTM)$

Emil Jeřábek

est l'inverse d'une fonction constructible dans le temps croissante et illimitée

(

nous avons). Vous pouvez le remplacer par une fonction sublinéaire honnête.

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