¿Es

Defina como la clase de idiomas que puede aceptar una máquina de Turing (multitapa) en el tiempo . (El " " es simplemente para simplificar la notación y evitar confusiones). Observe que no hay alrededor de . $\mathsf{DTIME}(f(n))$ $f(n) + 1$ $+ 1$ $O(\cdot)$ $f(n) + 1$

¿Es cierto que ? $\mathsf{DTIME}(n) = \mathsf{DTIME}(2n)$

Usando el teorema de aceleración lineal , podemos probar , pero ¿podemos llegar a ? $\mathsf{DTIME}(2n) = \mathsf{DTIME}(1.01n)$ $n$

Parece que el lenguaje de los palíndromos está en ; para temas relacionados, vea la publicación de blog de Lipton sobre algoritmos de cadena $\mathsf{DTIME}(n)$

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

En " Máquinas de Turing deterministas en el rango entre tiempo real y tiempo lineal " encontré: si

entonces

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

Bien, parece ser justo lo que estaba buscando. ¿Quieres convertirlo en una respuesta?

domotorp

pregunta interesante, pero objetar la redefinición de un DTIME de clase de complejidad estándar de una manera no estándar, sugiero que al menos lo llame algo así como DTIME 'para evitar confusiones

vzn

Este documento puede ser útil. [Rosenberg 67] Idiomas definibles en tiempo real dl.acm.org/citation.cfm?id=321423

zZzZzZ

¿Es

Respuestas: