Consecuencias del no determinismo que aceleran el cálculo determinista

8

Si nortePAGS contiene una clase de problemas de tiempo superpolinomial, es decir

para alguna función tnorteω(1) , ,reTyoMETROmi(t)nortePAGS

entonces, si se sigue del teorema de la jerarquía de tiempo determinista que .PAGSnortePAGS

Pero, ¿hay otras consecuencias interesantes no triviales (es decir, no una consecuencia de PAGSnortePAGS ) si el no determinismo puede acelerar los cálculos deterministas?

GMB
fuente
Disculpas si esta pregunta no es apropiada para este sitio. Estaré encantado de mejorar la pregunta como pueda.
GMB
Creo que esta es una pregunta interesante. Una consecuencia fácil similar a la separación de P de NP es que NP no está en DTime (o (t) / lg n).
Kaveh
PD: eliminé la segunda parte porque creo que es una distracción y no agrega mucho a la pregunta.
Kaveh
Gracias, Kaveh. ¡Realmente aprecio la edición! (y desde el cambio de voto, parece que todos los demás también lo hacen)
GMB

Respuestas:

2

Encontré una consecuencia relacionada.

Digamos que contiene , donde . Resulta que este es el tiempo suficiente para diagonalizar contra . Específicamente, construya la siguiente máquina:D T I M E ( 2 O ( t ) ) t = n ω ( 1 ) P / p o l ynortemiXPAGSreTyoMETROmi(2O(t))t=norteω(1)PAGS/ /pagsoly

En la entrada de longitud , considere el máquina de Turing . Para cada posible cadena de consejos de longitud y cada posible cadena de bits de longitud , ejecute en con el consejo , y rechace después de pasos si aún no ha aceptado. Registre sus resultados en una tabla. Este procedimiento se ejecuta en .n n t h M t b n M b a t D T I M E ( 2 O ( t ) )XnortenortethMETROt sinorteMETROsiunatreTyoMETROmi(2O(t))

En la entrada , si al menos la mitad de las cadenas de aviso hacen que rechace, entonces en su lugar definimos que es correcto que nuestro algoritmo lo acepte (de lo contrario, es correcto que nuestro algoritmo lo rechace). Las cadenas de consejos que causaron que se equivoque (es decir, al menos la mitad de las cadenas de consejos) ahora se eliminan de la tabla. Luego repetimos el proceso en la entrada : si al menos la mitad de las cadenas de consejos supervivientes hacen que rechace, entonces nuestro algoritmo aceptará (y rechazará lo contrario). Continúe así para todas las entradas de longitud (aunque realmente, solo0 0norteMETROMETRO0 0norte0 0norte-11METROnortet de ellos son necesarios, después de tantas entradas, hemos descartado todas las cadenas de consejos posibles).

Claramente, este lenguaje se puede decidir en , que asumimos que está en . Por otro lado, no puede estar en : el conjunto de entradas de longitud diagonaliza contra la perspectiva de que se use para decidir el idioma.reTyoMETROmi(2O(t))nortemiXPAGSPAGS/ /PAGSolyM nnorteMETROnorte

Entonces obtenemos , lo que sería interesante.nortemiXPAGSPAGS/ /pagsoly

Dejaré la pregunta abierta en caso de que a alguien se le ocurra algo más.

GMB
fuente