Si observamos el teorema de la jerarquía DTIME, tenemos un registro debido a la sobrecarga en la simulación de una máquina de Turing determinista por una máquina universal:
No tenemos este tipo de gastos generales para NTIME de DSPACE. Una justificación básica proviene de los detalles de la prueba al considerar la diferencia entre simuladores.
Mi pregunta es la siguiente: sin considerar los detalles de la prueba del teorema de la jerarquía DTIME, ¿hay una justificación de este registro o podría ser solo una consecuencia de la prueba y sería razonable imaginar que si luego
En mi opinión, considerar que la explicación de la simulación es una buena justificación debería justificarse demostrando que si tuviéramos un mejor resultado, podríamos crear una mejor simulación.
fuente
Respuestas:
El teorema de la jerarquía de tiempo es el tema de mi proyecto de diploma, tal vez desee ver los comentarios sobre mi pregunta Límites inferiores y separación de clases .
Mirando hacia atrás a esta pregunta y cómo se relaciona con lo que está preguntando, se me ocurrió una idea que podría mostrar que la sobrecarga de simulación TM de cinta múltiple a cinta simple que necesita la prueba del teorema no se puede mejorar. Por lo tanto, se necesita otro enfoque si deseamos mejorar este resultado.
EDITAR: Esta prueba es incorrecta, vea los comentarios a continuación para conocer el motivo exacto. Actualmente estoy editando la respuesta para reflejar eso.
Sea el idioma .A {0k1k|k≥0}
En una sola máquina de cinta, hay un algoritmo (puede encontrar detalles de este algoritmo en el capítulo 7.1.2 del libro de Sipser "Introducción a la teoría de la computación"). En la misma referencia, puede ver que un idioma está en o (n \ log n) si y solo si es regular. Kaveh también proporciona los documentos originales para este reclamo en la pregunta vinculada anteriormente.O(nlogn)
En los comentarios de mi pregunta, Ryan Williams ilustra un algoritmo para el mismo problema, utilizando una TM de 2 cintas.O(n)
Supongamos ahora que existe una técnica para simular una TM multitapa en una única TM de cinta que tiene un tiempo de ejecución de , donde es el tiempo de ejecución de la TM simulada . Al aplicarlo a la máquina que ilustra Ryan, obtendríamos una única cinta TM que se ejecutaría en . Por lo tanto, es regular, lo cual es una contradicción. Por lo tanto, concluimos que una sobrecarga de es lo mejor que podemos hacer al simular máquinas de cintas múltiples con máquinas de cintas individuales.o(T(n)logT(n)) T(n) o(nlogn) A logT(n)
Me doy cuenta de que esta es una declaración fuerte, por lo que podría estar equivocado en mi interpretación.
Incluso si existe una técnica que permita mejorar este resultado, creo que no es posible igualar el resultado para o . Mi intuición deriva del siguiente hecho:NTIME SPACE
Hay un resultado muy conocido que indica . Bajo el supuesto de que , creo que este resultado se mejora a , para cualquier . Entonces, una clase no determinista muy pequeña es mucho más poderosa que cualquier determinista . Entonces, dado lo poderoso que es un recurso de tiempo no determinista, esperaría que se necesitara una mayor cantidad de tiempo determinista para hacer que un TM sea más poderoso para compensar el poder del no determinismo.DTIME(n)≠NTIME(n) P≠NP DTIME(nk)≠NTIME(n) k
fuente
Para las TM n-tape, Furer demostró en 1982 un resultado de jerarquía temporal similar al teorema de la jerarquía espacial. El factor no es necesario.lg
El factor para el teorema de la jerarquía de tiempo indicado en su publicación es solo para TMs de una sola cinta. A menos que esté muy comprometido con el modelo de una sola cinta por alguna razón, no hay una diferencia entre el espacio y el tiempo con respecto a los teoremas de jerarquía.lg
Hay algunas razones y argumentos para usar TM de una sola cinta para definir clases de complejidad de tiempo, pero el uso de TM de una sola cinta para definir clases de complejidad no es universal, por ejemplo, ver Lance Fortnow y Rahul Santhanam [2007] donde usan cinta múltiple TMs.
La referencia original para el teorema de la jerarquía temporal es Hennie y Stearns [1966]. Demuestran el teorema de las máquinas de dos cintas. La teoría clásica de la recurrencia de Odifreddi los cita a ellos ya Hartmanis [1968] y describe una prueba que se parece a la del libro de Sipser.
Sin embargo, la prueba de TMs de una sola cinta en el documento de Hartmanis no utiliza simplemente la simulación. Distingue entre dos casos: 1. tiempo de ejecución siendo y 2. tiempo de ejecución siendo .o ( n 2 )Ω(n2) o(n2)
Para el primer caso, usa una simulación, y parece que uno puede deshacerse del factor si las simulaciones se pueden hacer de manera más eficiente.lg
Para el segundo caso, el documento proporciona directamente un lenguaje para la separación y no utiliza simulación en absoluto. Esto utiliza propiedades particulares de TMs de una sola cinta con tiempo de ejecución subcuadrático.
Hay que tener en cuenta que las TM de una sola cinta con el tiempo no son tan robustas y hay límites inferiores cuadráticos (por ejemplo, para Palindroms) en las TM de una sola cinta, mientras que una TM de dos cintas puede resolver estos problemas en el tiempo lineal.o(n2)
Como dije anteriormente, a menos que esté comprometido con el modelo de una sola cinta TM por alguna razón, incluso cuando el tiempo es subcuadrático, no hay un vacío que llenar, el teorema de la jerarquía del tiempo es lo más ajustado posible.
PD: si estamos utilizando TM de cintas múltiples, es decir, una máquina de Turing en la clase puede tener un número fijo pero arbitrario de cintas El resultado de Fürer no se aplica.
fuente
Para un número fijo de cintas mayor que uno, ) para construible en el tiempo . La sobrecarga logarítmica proviene del teorema de reducción de la cinta, donde cualquier cantidad de cintas se puede convertir en dos cintas (o incluso una sola cinta y una pila y con solo movimiento inconsciente).fTime(o(f))⊊Time(O(f) f
Si el número de cintas no es fijo, realmente no tenemos una técnica para demostrar constructivamente sin pasar por el teorema de reducción de cinta. Es posible que por cada , las máquinas de cintas no puedan ser simuladas por máquinas de cintas sin una sobrecarga logarítmica.DTime(g)⊊DTime(f) k k+1 k
Sin embargo, eso no significa que el teorema de la jerarquía de tiempo no pueda mejorarse o que falle.DTime(o(f))⊊DTime(O(f))
De hecho, ya tenemos lo siguiente.
Teorema: para cada y cada de la forma ( y racional; o ), .ε>0 f na(logn)b a b a>1 a=1∧b≥0 DTime(O(f/(logf)ε)⊊DTime(O(f))
Prueba: si cada idioma con un algoritmo de decisión puede decidirse en el tiempo , entonces rellenando la entrada, cada idioma con un algoritmo de decisión se puede decidir en tiempo (donde está fijo ), y así por cada constante , , contradiciendo el teorema de la jerarquía del tiempo.O(f) O(f/(logf)ε) O(f(n)(logf(n))kε) O(f(n)(logf(n))(k−1)ε) k≥0 c≥0 DTime(O(f(n)(logf(n))c))=DTime(O(f(n)))
Sin embargo, esta prueba no constructiva tiene tres limitaciones:f
DTime(O(f)) DTime(O(f/(logf)ε) k k DTime(O(f/(logf)ε) ε=1 f(n)=n2 k
DTime(O(f/(logf)ε) fallará para alguna entrada, pero no hemos demostrado que falle para alguna entrada para todos pero finitamente muchos tamaños de entrada (aunque sería muy sorprendente si no fuera así)
* La prueba requiere que tenga un buen comportamiento (no solo constructivo en el tiempo, sino también en cierto sentido continuo). * No conocemos un idioma en particular que esté en pero no en . Para una suficientemente grande , simulación de máquinas de Turing -tape no está en , pero no han descartado que incluso para y , lo menos que es> BB (BB (1000)) donde BB es la función de castor ocupado. * No sabemos que la inclusión sea robusta.
fuente